Among n + 1 integers from 1, 2, . . . , 2n, can we prove that there are

two which are relatively prime.

Printable View

- Apr 26th 2010, 09:20 AMStatsnoob2718Relatively prime integers
Among n + 1 integers from 1, 2, . . . , 2n, can we prove that there are

two which are relatively prime. - Apr 26th 2010, 09:49 AMbecko
By the pigeonhole principle.

Put the integers from 1 to 2n in bins, where each bin contains one integer and its successor.

bin1 = {1,2}

bin2 = {3,4}

...

bin(n) = {2n-1,2n}

There are n bins. If you take n + 1 integers from the set 1,2,...,2n, you are forced to take two integers from the same bin (pigeonhole). Since k and k + 1 are relatively prime, these two integers will be relatively prime.