# Least common multiple

667pages on
this wiki

The least common multiple of two given natural numbers is the smallest positive integer that is a multiple of both given numbers.

The product of any two numbers a and b is equal to the product of their greatest common divisor and least common multiple.

Proof: GCD(a,b) · LCM(a,b) = ab

Prerequisites:
• Proof that the prime factorization of an integer is unique
• Maximum and minimum
• Proof that the minimum exponent of each factor in the factorization of two integers make up the factorization of their greatest common divisor.
• Proof that the maximum exponent of each factor in the factorization of two integers make up the factorization of their least common multiple.

If a = 1, then GCD(a,b) = 1 and LCM(a,b) = b, then GCD(1,b)· LCM(1,b) = 1·b = b, which is already equal to ab.

The same goes when b = 1. The conclusion is now true when either a or b is equal to 1.

We now list the prime factorizations of the numbers:

$a = {f_1}^{c_1} {f_2}^{c_2} ... {f_p}^{c_p}$ and $b = {g_1}^{d_1} {g_2}^{d_2} ... {g_q}^{d_q}$

If a factor $f_i$ or $g_i$ is not in the other factorization, we add them to the other factorization by assigning their exponents a zero. Thus, the number of factors should now be equal, and no distinction will be made between the factorizations:

$a = {k_1}^{c_1} {k_2}^{c_2} ... {k_n}^{c_n}$, and
$b = {k_1}^{d_1} {k_2}^{d_2} ... {k_n}^{d_n}$.

Let's take an example. Suppose a=12 and b=16. Their factorizations are:

$12 = 2^2 \cdot 3^1$ and
$16 = 2^4$.

Now since the factor 3 is not in 16, we'll add that to the factorization of 16 with an exponent of 0:

$16 = 2^4 \cdot 3^0$

We don't have anything to change in the factorization of 12.

Using the last two proofs stated in the prerequisites, we have:

$GCD(a,b) = k_1^{min(c_1,d_1)} \cdots k_n^{min(c_1,d_1)}$, and
$LCM(a,b) = k_1^{max(c_1,d_1)} \cdots k_n^{max(c_1,d_1)}$

Multiplying,

$GCD(a,b) \cdot LCM(a,b) = [k_1^{min(c_1,d_1)} \cdots k_n^{min(c_1,d_1)}] \cdot [k_1^{max(c_1,d_1)} \cdots k_n^{max(c_1,d_1)}]$
$= k_1^{min(c_1,d_1)+max(c_1,d_1)} \cdots k_n^{min(c_n,d_n)+max(c_n,d_n)}$

Evaluating $min(x,y) + max(x,y)$, we would find out that it is just equal to $x+y$, since one of them would be the minimum and the other would be the maximum, and it still holds when $x = y$.

$= k_1^{c_1 + d_1} \cdots k_n^{c_n + d_n}$
$= [k_1^{c_1} \cdots k_n^{c_n}][k_1^{d_1} \cdots k_n^{d_n}]$

Recall that the above expressions are equal to a and b.

$= ab$

QED