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 solution | Comment 2 of 7 |

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
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information