Thread: Relatively prime integers

Among n + 1 integers from 1, 2, . . . , 2n, can we prove that there are
two which are relatively prime.

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.