Wikia

Math Wiki

Least common multiple

Talk0
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

See alsoEdit

Around Wikia's network

Random Wiki