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

The only possible prime factors the ten numbers might share are 2, 3, 5 and 7.  The positions of multiples of these primes within any given range (including ranges of 10) therefore shift in a cycle of 2*3*5*7=210 numbers.  Therefore we can check the first 220 numbers to find those numbers that do not have any one of these as a factor.  They are listed below, together with the difference between it at the previous number on the list:

  1
 11   10
 13    2
 17    4
 19    2
 23    4
 29    6
 31    2
 37    6
 41    4
 43    2
 47    4
 53    6
 59    6
 61    2
 67    6
 71    4
 73    2
 79    6
 83    4
 89    6
 97    8
101    4
103    2
107    4
109    2
113    4
121    8
127    6
131    4
137    6
139    2
143    4
149    6
151    2
157    6
163    6
167    4
169    2
173    4
179    6
181    2
187    6
191    4
193    2
197    4
199    2
209   10
211    2

None of the differences is greater than 10, so every group of ten will have at least one.

In fact, there are only two points in the cycle where the distance is farther than 8: 1-11, and 199-211.  In the first instance (to be repeated  at 211-221), 7 (or 217) is the only multiple of that number within the group bounded by numbers on the list and so serves as a relative prime until 1 (or 211) is reached on the one side or 11 (or 221) on the other.  In the other range, 199-211, 203 is a multiple of only 7 and again the only such multiple in the range, and so serving as a relative prime within that group.

Thus any set of eight consecutive integers has at least one member that is relatively prime to the others in the set.

Edited on March 3, 2004, 9:10 am

Posted by Charlie on 2004-03-03 09:07:57