Egyptian Divisibility

Problem

A group of Archaeologists discovered some simple hieroglyphs on the stone lid of a tomb in Egypt. When they translated them they realised that it was a four digit number, but more remarkably it is the smallest number that can be divided by all of the numbers from 1 to 10 without any remainder. What was that number?

Solution

By considering the prime factors of each of the numbers from 1 to 10:

2 = 2
3 = 3
4 = 2x2
5 = 5
6 = 2x3
7 = 7
8 = 2x2x2
9 = 3x3
10 = 2x5

We can deduce that the smallest number which evenly divides 2, 3, 4, ... , 10, must be 2 3 2 5 7 2 3 = 2520.

Alternatively we can consider which factors from 1 to 10 are necessary. A factor of 8 deals with 2, 4 and 8. 9 deals with 3 and 9. So 9 8 = 72, which immediately deals with 6 (shared factors of 2 and 3), but we still need this number to be divisible by 5, 7 and 10. As 72 contains a factor of 2, using a factor of 5 makes it divisible by 10. Hence the smallest number must be 72 5 7 = 2520.

Problem ID: 112 (Apr 2003)     Difficulty: 2 Star

Only Show Problem