Counting and Pigeonhole, Incl- Excl

[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

The Attempt at a Solution

In boxes does it mean to write:

[1,2]
[2,3]
[3,4]
[4,5]
[5,6]
[6,7]...

and i don't understand how two consecutive integers are relatively prime.

 

[Mark44]

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

The Attempt at a Solution

In boxes does it mean to write:

[1,2]
[2,3]
[3,4]
[4,5]
[5,6]
[6,7]...

and i don't understand how two consecutive integers are relatively prime.

When you post a question and no one responds, you can "bump" the post and provide additional information, but don't start another thread about the same problem.

I believe the hint means to label the boxes so they are distinct, like so...
[1,2]
[3,4]
[5,6]
[7,8]
[9,10]
[11,12]
.
.
.
[2n-1,2n]

For any two consecutive integers, one must be even and the other odd, so they can't be divisible by 2. If one is divisible by 3, the other one can't be, because they're only 1 apart. Similarly, both can't be divisible by 5, 7, 11, 13, and so on. We don't need to check 4, 6, 8, and so on, or any other multiple of 2, since one of the numbers isn't even. We also don't need to check multiples of 3, or 4, or 5, or ...

 

[awkward]

Suppose d divides n and n+1.
Then d must divide (n+1) - n = 1.
So d must be plus or minus 1.