Expert: Josh - 2/28/2006

Question
How do I find the least common multiple of three or more numbers

Answer
Hi Gary,

The following is a two-step procedure for finding the least common multiple.

Step 1: Factorize each number in terms of prime factors.
Step 2: Find the smallest product of prime numbers that is divisible by all numbers. (need to identify the missing terms in the prime factorization for each number.)

Don't worry if this makes little sense right now, I'll give you an example showing you exactly what this means.

Illustration:
What is the LCM of 15,20 and 6?

List of the first ten prime numbers P={2,3,5,7,11,13,17,19,23,29,.....}

Step 1: Express each number in the example as a product of prime numbers (Note: We simply factorize each number in terms of the prime numbers in the set P. A repeat of the same prime number is permitted in the factorization; this is called multiplicity.)

Procedure: Begin with the smallest prime number from the set P. We denote this with "p". Effectively, we start with p=2. Try dividing "N", the number you are considering by p if possible. If p does not divide N, pick the next larger prime number from the set P, and let this be p. Repeat this process, until p > N or you are left with a prime number.

Let N=15, p=2. Two does NOT divide 15. Cross out 2 from P={2,3,5,7,9,11,13,17,19,23,29...}. The next larger prime is p=3. Now, three divides 15, we have 15=3*5.
Let N'=5. N' is itself a prime number, so nothing more to be done. We end up with the prime factorization, 15=3*5.

Let N=20, p=2. This time, two divides 20. Intermediate result is 20=2*10. Now, let N'=10. Does 2 divide 20? Yes. So, we write 20=2*2*5. Next, let N"=5. Once again, we can proceed no further. Since we end up with five, a prime factor. Thus, 20=2*2*5 is the unique prime factorization for the number twenty.

Let N=6, p=2. Obviously, two divides 6. Intermediately, we get 6=2*3. Let N'=3. N' cannot be divided by any number other than 1 and itself. Three is a prime number in the set P. So, we can go no further. Thus, the unique prime factorization for six is 6=2*3.

Summary: 15=3*5, 20=2*2*3=(2^2)*3, 6=2*3.

Step 2: Find the smallest product of prime numbers that is divisible by all three numbers. This is actually very easy to do, once we obtained the prime factorization.

Aside: Compare
L=3*5  ...[#1]
M=2*2*3...[#2]
N=2*3  ...[#3]
Clearly, the term "2" is missing from L.
Let L'=2*3*5. Observe that M contains a factor 2, with multiplicity of 2. i.e., the prime factor two appears twice in M. Still, we need to multiply L' by 2, so that L has the same component as M.
Let L" = L*2 = 2*2*3*5.

Next, compare L" with N. Is there anything in N that L" doesn't have? Look carefully! L"=2*2*3*5, while M=2*3.
Conclusion: L" already contains all the prime factors appearing in both M and N. So, we are done.

L"=2*2*3*5=60 is the LEAST COMMON MULTIPLE for 15,20 and 6.

With practice, you'll find that this is actually an elegant procedure. There's nothing to it. You can describe the procedure in various ways. The important thing is that you understand how to apply it.

Go over the example until it sinks in. Let me know if anything is unclear.

Cheers.

Josh, Australia.