Prime Factors Problem 1: LCM

I’ve been looking over ProjectEuler.net and found a few fun problems involving factoring and prime numbers. This first one is easy for computer and math geeks, but should be do-able by anyone with a calculator and a recollection of factoring. I’ll go through it step-by-step.

Find the smallest number divisible by all integers between 1 and n, where n > 2.

This is based on “Problem 5” of Project Euler, but before you look at the page, first try attacking an easy case. When n is 3, it’s painfully easy. 1 x 2 x 3 = 6, so 6 is is it. Try an interesting value. Let n = 10.

What is the smallest number divisible by all integers between 1 and 10?

Go ahead and think about how you might solve this. (Hint: title of this post.)

Number theory

You’ve likely encountered this problem in reverse back in secondary education about factoring numbers. Given a number, find the smallest factors, which will all be prime. What we want to do is find the fewest prime factors satisfying the question and multiply. Why?

Theorem: Given integers a, b, and c, if a divides b and b divides c, then a divides c.

I’ll leave the proof writing for homework. It’s easy to see this transitive association, though. 2 divides 6 and 6 divides 12, so 2 divides 12. Since we want to find the smallest number, we don’t want to duplicate common factors. 12 is factored into 3 x 4, and 8 factored is 2 x 4, so by our divisibility rule, smallest number divisible by both 8 and 12 is 3 x 4 x 2 = 24. This smallest number, 24, is also known as the least common multiple (LCM) of 8 and 12. When working with multiples of more integers, it’s easier to use prime factors such as 12 = 3 x 2 x 2.

Notice if you had multiplied all factors of 8 and 12 (3 x 4 x 2 x 4 = 96 = 8 x 12) you’ll get a larger number divisible by 8, 12, and also the LCM, 24.

Theorem: Given non-zero integers a, b, and c, if a divides c and b divides c, then LCM(a,b) divides c.

Theorem: Given integer n > 1, then n can be written as a product of primes.

Solution

Find prime factors for integers 1 - 10:

• 1: 1 divides all numbers.
• 2: Is prime.
• 3: Is prime.
• 4: 2 x 2
• 5: Is prime.
• 6: 2 x 3
• 7: Is prime.
• 8: 2 x 4 = 2 x 2 x 2
• 9: 3 x 3
• 10: 2 x 5

To find the least common multiple of 1-10, all we do is multiply the fewest prime factors from the table above. A number divisible by 4 is divisible by 2, but not every number divisible by 2 is divisible by 4. We need 2 x 2. We can skip 6 since any number divisible by 6 is also divisible by 2 and 3 which we have. Since 8 = 2 x 2 x 2, we’ll need another 2. For 9, we’ll need another 3, and 10 we have covered. I’ve multiplied the fewest factors in counting order with bold representing the missing prime factor, or 1.

1 x 2 x 3 x 2 x 5 x 1 x 7 x 2 x 3 x 1 = 2520.

2520 is divisible by every integer between 1 and 10, and is the smallest such number since it is made of up the fewest prime factors satisfying divisibility of 1-10.

“Problem 5” actually asks for when n = 20. Go ahead and give it a try with a calculator.

For the general case, you could write a program function to count up to n multiplying prime factors as needed. Check your work with n = 10 and n = 20.

For theorems and proofs, see Elementary Number Theory by Charles Vanden Eynden.