Prove that at least one integer in any set of ten consecutive integers is relatively prime to the others in the set.

To prevent a given number from being relatively prime to the rest in the set of ten, it must share a prime factor. Prime factors that are 11 or larger need not be considered, as only one number in any range of ten can have such a prime as a factor.

In any span of ten numbers, five will be even (divisible by 2), leaving five that are still possible candidates for being relatively prime. There can be three numbers that contain 3 as a factor, but at least one of these was already disqualified by being even, so the 3's can only reduce the candidates by 2, leaving 3 candidates for relative primeness.

Only two of the numbers in the range can be divisible by 5, but again, one is even, so only one is removed from candidacy now, leaving 2 candidates.

At most two numbers in the range can be divisible by 7, and again, only one can be odd, so at most one candidate is disqualified, leaving at least one that's still relatively prime to the rest.

As we've run out of primes under 11, we've shown that at least one number of the ten is relatively prime to the rest.

Posted by Charlie on 2004-03-03 08:37:43