Editing Least common multiple (section)

=== Lattice-theoretic ===
The positive integers may be [[partially ordered]] by divisibility: if ''a'' divides ''b'' (that is, if ''b'' is an [[integer multiple]] of ''a'') write ''a'' ≤  ''b'' (or equivalently, ''b'' ≥ ''a''). (Note that the usual magnitude-based definition of ≤ is not used here.)

Under this ordering, the positive integers become a [[lattice (order)|lattice]], with [[meet (mathematics)|meet]] given by the gcd and [[join (mathematics)|join]] given by the lcm. The proof is straightforward, if a bit tedious; it amounts to checking that lcm and gcd satisfy the axioms for meet and join. Putting the lcm and gcd into this more general context establishes a [[duality (order theory)|duality]] between them:

:''If a formula involving integer variables, gcd, lcm, ≤ and ≥  is true, then the formula obtained by switching gcd with lcm and switching  ≥  with ≤ is also true.'' (Remember ≤  is defined as divides).

The following pairs of dual formulas are special cases of general lattice-theoretic identities.

{| style="margin:0;" cellpadding="0" border="0" cellspacing="0"
|
;[[commutative operation|Commutative laws]]
:<math>\operatorname{lcm}(a, b) = \operatorname{lcm}(b, a),</math>
:<math>\gcd(a, b) =\gcd( b, a).</math>
| &nbsp;&nbsp;&nbsp;&nbsp;
|
;[[associativity|Associative laws]]
:<math>\operatorname{lcm}(a,\operatorname{lcm}(b, c)) = \operatorname{lcm}(\operatorname{lcm}(a , b),c),</math>
:<math>\gcd(a, \gcd(b, c)) = \gcd(\gcd(a,b), c).</math>
| &nbsp;&nbsp;&nbsp;&nbsp;
|
;[[Absorption law]]s:
:<math>\operatorname{lcm}(a, \gcd(a,b)) = a,</math>
:<math>\gcd(a, \operatorname{lcm}(a, b)) = a.</math>
|}

{| style="margin:0;" cellpadding="0" border="0" cellspacing="0"
|
;[[Idempotent|Idempotent laws]]
:<math>\operatorname{lcm}(a, a) = a,</math>
:<math>\gcd(a, a) = a.</math>
| &nbsp;&nbsp;&nbsp;&nbsp;
|
;[[Lattice (order)#Connection between the two definitions|Define divides in terms of lcm and gcd]]
:<math>a \ge b \iff a = \operatorname{lcm}(a,b),</math>
:<math>a \le b \iff a = \gcd(a,b).</math>
|}

It can also be shown<ref>The next three formulas are from Landau, Ex. III.3, p. 254</ref> that this lattice is [[distributive lattice|distributive]]; that is, lcm distributes over gcd and gcd distributes over lcm:

:<math>\operatorname{lcm}(a,\gcd(b,c)) = \gcd(\operatorname{lcm}(a,b),\operatorname{lcm}(a,c)),</math>
:<math>\gcd(a,\operatorname{lcm}(b,c)) = \operatorname{lcm}(\gcd(a,b),\gcd(a,c)).</math>

This identity is self-dual:
:<math>\gcd(\operatorname{lcm}(a,b),\operatorname{lcm}(b,c),\operatorname{lcm}(a,c))=\operatorname{lcm}(\gcd(a,b),\gcd(b,c),\gcd(a,c)).</math>