Least common multiple
Talk0this wiki
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:
- and
If a factor or 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:
- , and
- .
Let's take an example. Suppose a=12 and b=16. Their factorizations are:
- and
- .
Now since the factor 3 is not in 16, we'll add that to the factorization of 16 with an exponent of 0:
We don't have anything to change in the factorization of 12.
Using the last two proofs stated in the prerequisites, we have:
- , and
Multiplying,
Evaluating , we would find out that it is just equal to , since one of them would be the minimum and the other would be the maximum, and it still holds when .
Recall that the above expressions are equal to a and b.
QED