Relatively Prime Integers in a Set: Pigeonhole Principle

[snaidu228]

Homework Statement

Prove that, in any set of n + 1 positive integers (n ≥ 1) chosen from the set {1, 2, . . . 2n}, it must be that two of them are relatively prime (i.e. have no common divisor except 1). ( Hint: two consecutive integers are relatively prime. Make boxes labelled by pairs of consecutive integers. ).

Homework Equations

pigeonhole

The Attempt at a Solution

 

[LCKurtz]

That's a pretty good hint. What have you tried or what ideas do you have? We aren't here to work it for you.