# Math Help - Primes

1. ## Primes

Prove that if one chooses more than n numbers from the set $\lbrace1, 2, 3, . . . , 2n\rbrace,$ then two of them are relatively prime.

2. Partition them as $\{1,2\},\ \{3,4\},\ \hdots,\{2n-1,2n\}$. Since there are $n$ parts, one part must contain two of the numbers, and hence two of the numbers are adjacent. Since adjacent numbers are relatively prime we are done.