What is the Common Divisor Question?

[rbzima]

Homework Statement

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.

Homework Equations

None

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!