Prove that in any set of $n+1$ positive numbers not exceeding $2n$ there must be two that are relatively prime.
To prove there exist two relatively prime numbers in a finite set
7
$\begingroup$
combinatorics
-
5This is an old problem. Without giving too much away, have you thought about how you could definitely tell that two numbers are coprime? And maybe the bounds you are given may suggest using the pigeonhole principle? I think this is one you should work at before asking it. – 2011-07-02