Wikia

$Ambox notice$

This page should be merged with L.C.M. and H.C.F.

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$ .