2

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!

Evgeny Kuznetsov
  • 1,044
xael
  • 21

2 Answers2

4

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.

Matt Samuel
  • 58,164
  • Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right? – xael Dec 10 '14 at 02:18
  • Totally got it now. Thanks – xael Dec 10 '14 at 12:51
  • @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out. – Matt Samuel Dec 10 '14 at 16:22
4

Picking on Matt Samuel's answer, the reason for which it works is that, if the prime divisors of $a,b,c \in \mathbb N$ are $p_1, \ldots, p_n$, so that

$$a=p_1^{i_1}\cdot \cdots \cdot p_n^{i_n}, \quad b=p_1^{j_1}\cdot \cdots \cdot p_n^{j_n}, \;\text{ and }\; c=p_1^{k_1}\cdot \cdots \cdot p_n^{k_n},$$

with $i_r,j_r,k_r \geq 0$, for $1\leq r \leq n$, then

$$\gcd\{a,b\} = p_1^{\alpha_1}\cdot \cdots \cdot p_n^{\alpha_n}\quad\text{and}\quad\mathrm{lcm}\{a,b\} = p_1^{\beta_1}\cdot \cdots \cdot p_n^{\beta_n},$$

where $\alpha_r = \min\{i_r,j_r\}$ and $\beta_r=\max\{i_r,j_r\}$.

Since, for $u,v,w \in \mathbb N$ $$\max\{ \min\{u,v\}, \min\{u,w\} \} = \min\{ u, \max\{v,w\} \}$$ (easy to check), it follows that $$\gcd\{ a,\mathrm{lcm}\{b,c\} \} = \mathrm{lcm}\{ \gcd\{a,b\}, \gcd\{a,c\} \},$$ that is, $$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c),$$ taking "$\gcd$" as "$\wedge$" and "$\mathrm{lcm}$" as "$\vee$", with infix notation.

amrsa
  • 12,917