Common Divisor Question...

[rbzima]

1. The problem statement, all variables and given/known data

We select n + 1 different integers from the set {1,2,...,2n}. Prove that there will always be two among the selected integers whose largest common divisor is 1.

2. Relevant equations

None

3. The attempt at a solution

I was thinking that this problem has something to do with the pigeonhole principle, however I'm pretty stuck here and don't even know where to get started...

[foxjwill]

You're correct that it uses the pigeonhole principle.

What are the possible gcd's for an arbitrary pair of integers from the set {1,2,...,2n}?

[rbzima]

Figured it out... Thanks for the help...

Essentially, gcd(k, k+1) is a good candidate! =)

[foxjwill]

Exactly!