# Show N has Prime Numbers

by C R P
Tags: college, loot, math, proof, relatively prime
 P: 5 (For the following problem I don't just want a flat out answer, but steps and Ideas on how to solve it. The problem was given by my Universities newspaper and for solving it you get free Loot and stuff) ---------------------------------------------------------------------------------------------------------------------------------------- The Problem: Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers, contains at least one pair of relatively prime numbers. relatively prime means: "Two integers are relatively prime if they share no common positive factors (divisors) except 1" Example: 8 and 15 are relatively prime. 8 = 2 * 2 * 2 15 = 3 * 5 Example: 9 and 12 are NOT relatively prime 9 = 3 * 3 12 = 2 * 2 * 3 ---------------------------------------------------------------------------------------------------------------------------------------- My thinking thus far: None really I've just started
 P: 361 Hint: If m is a positive integer, then m and m+1 are relatively prime.
P: 5
 Quote by Petek Hint: If m is a positive integer, then m and m+1 are relatively prime.
very true, but I think the problem is more difficult than this.

"Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers"

wouldn't this mean the set would be...
n= 0 1 2 3 4
Set=0,2,6,8

then you would do the n+1 one on that set?
Or something to that extent?

 Homework Sci Advisor HW Helper Thanks P: 9,656 Show N has Prime Numbers Petek's hint is right. If you wanted to choose a subset without picking any pair that's relatively prime, what does that tell you about the option of picking consecutive numbers from the set?