[Math] Show natural numbers ordered by divisibility is a distributive lattice.

divisibilitylattice-ordersnatural numbers

I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with $\operatorname{gcd}$ as "$\wedge$" and $\operatorname{lcm}$ as "$\vee$".

I know that for a general lattice it can be shown that
$$a \wedge (b \vee c) \geq (a \wedge b) \vee (a \wedge c)$$ and if we can show the opposite, that
$$a \wedge (b \vee c) \leq (a \wedge b) \vee (a \wedge c)$$
then the two are equal. How do I prove this second part?

I am not experienced with number theory, and I have struggled to get a meaningful expression of $\operatorname{gcd}$'s and $\operatorname{lcm}$'s.

Alternatively, is there a different way you can show me how to prove this?

Thank you!

Best Answer

We will construct a function from the natural numbers onto a distributive lattice, namely the lattice of all infinite sequences of natural numbers, all but finitely many of which are 0, with coordinatewise maximum as the join and coordinatewise minimum as the meet. The function is a lattice isomorphism. Let $p_1,p_2,\ldots$ be all prime numbers indexed in order. If $$n=p_1^{i_1}p_2^{i_2}\cdots$$ map $n\mapsto (i_1,i_2,i_3,\ldots)$. Then this is a lattice homomorphism, join corresponds to LCM and meet corresponds to GCD.

If you can't use this answer directly, consider this as a hint that LCM means you are taking the maximum of all powers of particular primes among the two numbers and GCD means you're taking the minimum.

Related Question