Editing Least common multiple (section)

== Formulas ==

=== Fundamental theorem of arithmetic ===
According to the [[fundamental theorem of arithmetic]], every integer greater than 1 can be represented uniquely as a product of prime numbers, [[up to]] the order of the factors:

:<math>n = 2^{n_2} 3^{n_3} 5^{n_5} 7^{n_7} \cdots = \prod_p p^{n_p},</math>

where the exponents ''n''<sub>2</sub>, ''n''<sub>3</sub>, ... are non-negative integers; for example, 84 = 2<sup>2</sup> 3<sup>1</sup> 5<sup>0</sup> 7<sup>1</sup> 11<sup>0</sup> 13<sup>0</sup> ...

Given two positive integers <math display="inline">a = \prod_p p^{a_p}</math> and <math display="inline">b = \prod_p p^{b_p}</math>, their greatest common divisor and least common multiple are given by the formulas
:<math>\gcd(a,b) = \prod_p p^{\min(a_p, b_p)}</math>

and
:<math>\operatorname{lcm}(a,b) = \prod_p p^{\max(a_p, b_p)}.</math>

Since
:<math>\min(x,y) + \max(x,y) = x + y,</math>
this gives
:<math>\gcd(a,b) \operatorname{lcm}(a,b) = ab.</math>

In fact, every rational number can be written uniquely as the product of primes, if negative exponents are allowed. When this is done, the above formulas remain valid. For example:
:<math>\begin{align}
  4 &= 2^2 3^0,                   & 6 &= 2^1 3^1,    & \gcd(4, 6) &= 2^1 3^0 = 2,    & \operatorname{lcm}(4,6) &= 2^2  3^1 = 12. \\[8pt]
  \tfrac{1}{3} &= 2^0 3^{-1} 5^0, & \tfrac{2}{5} &= 2^1 3^0 5^{-1}, & \gcd\left(\tfrac13, \tfrac{2}{5}\right) &= 2^0 3^{-1} 5^{-1} = \tfrac{1}{15}, & \operatorname{lcm}\left(\tfrac{1}{3}, \tfrac{2}{5}\right) &= 2^1 3^0 5^0 = 2, \\[8pt]
  \tfrac{1}{6} &= 2^{-1} 3^{-1},  & \tfrac{3}{4} &= 2^{-2} 3^1, & \gcd\left(\tfrac{1}{6}, \tfrac{3}{4}\right) &= 2^{-2} 3^{-1} = \tfrac{1}{12}, & \operatorname{lcm}\left(\tfrac{1}{6}, \tfrac{3}{4}\right) &= 2^{-1} 3^1 = \tfrac{3}{2}.
\end{align}</math>

=== 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>

=== Other ===
* Let ''D'' be the product of ''ω''(''D'') distinct prime numbers (that is, ''D'' is [[squarefree]]).

Then<ref>Crandall & Pomerance, ex. 2.4, p. 101.</ref>

:<math>|\{(x,y) \;:\; \operatorname{lcm}(x,y) = D\}| = 3^{\omega(D)},</math>

where the absolute bars || denote the [[cardinality]] of a set.

* If none of <math>a_1, a_2, \ldots , a_r</math> is zero, then

:<math>\operatorname{lcm}(a_1, a_2, \ldots , a_r) = \operatorname{lcm}(\operatorname{lcm}(a_1, a_2, \ldots , a_{r-1}), a_r). </math><ref>{{harvtxt|Long|1972|p=41}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=58}}</ref>