All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Not So Neighborly (Posted on 2004-03-03) Difficulty: 4 of 5
Prove that at least one integer in any set of ten consecutive integers is relatively prime to the others in the set.

See The Solution Submitted by Aaron    
Rating: 4.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Another proof--and extension. | Comment 5 of 7 |

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information