# Prove using Pigeon Hole

Prove that if select $101$ integers from the set $S = \{1,2,3,...,200\}$, there exist $m,n$ in the selection where $\gcd(m,n) = 1$!

Any hint how to prove this?

-
Two must be consecutive. –  Robert Feb 6 '13 at 6:27
Divide $S$ into $100$ pairs in such a way that the members of each pair are relatively prime. –  Brian M. Scott Feb 6 '13 at 6:28
Consider the partition of $\{1,2,\ldots,200\}$ into $100$ partitions $$\{1,2\},\{3,4\},\{5,6\}, \ldots,\{199,200\}$$ By pigeon-hole principle, we have two numbers in one partition say $2n-1$ and $2n$. The $\gcd$ of this pair is $1$ since if $d \vert (2n)$ and $d \vert (2n-1)$, then $d \vert (2n-(2n-1))$ i.e. $d \vert 1$. Hence, $$\gcd(2n-1,2n) = 1$$