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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityProve 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?
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$$