2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Relatively prime is another term for coprime. $\endgroup$ – Batman Dec 17 '15 at 5:05
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.