# Finding relatively prime numbers in a bounded list

Choose any 100 whole numbers between 1 and 200 inclusive. It is possible that there is not a single pair of numbers that are relative prime among these 100. For example, if one were to choose all even numbers in this range--there are exactly 100 of them--since each number is divisible by 2, then no two among the 100 will be relatively prime.

However, if one were to choose 101 numbers from the range 1 - 200 inclusive, it is guaranteed that there will be at least one pair of relatively prime numbers. Prove it!

• Relatively prime is another term for coprime. – Batman Dec 17 '15 at 5:05

By choosing 101 numbers it is guaranteed that two consecutive numbers must be chosen, a simple grouping would be $(1,2)(3,4)(5,6)...(199,200)$ and by pigenhole principal one group must have both elements chosen.

If $1$ is chosen we're done: $\gcd(1,n)=1$ for any $n$. If not we've chosen $101$ numbers between $2$ and $200$, and so somewhere we've chosen two adjacent numbers $n$ and $n+1$. We have $n+1-n=1$, so $\gcd(n,n+1)=1$.

If you don't feel sure that we must have two adjacent numbers in $n+1$ which were taken from $2$ to $2n$, assume that there are indeed $n+1$ nonadjacent numbers there. If $a$ is the smallest number taken, then the next nonadjacent number is $\geq a+2$, the next after that is $\geq a+4$, and so forth until the $(n+1)$st is $\geq a+2n$. Since $a\geq 2$ and we are taking numbers from $2$ to $2n$, the $(n+1)$st is too large to fit, and we have our contradiction.