# Pigeonhole principle- Show that two co-prime integers exist

Suppose that you are given $n + 1$ different positive integers less than or equal to $2n$. Show that there must exist two which are relatively prime.
The book provides a nice hint which is difficult to come up with : Prove instead that there are two consecutive numbers. So, my solution differs a bit.
It would be great if someone could proof-read my solution which goes as follows:

If two numbers $a,b$ are not co-prime, then $\exists$ prime $p : p|a, p|b$. Therefore, both the elements must be two of $\lceil{\frac{2n}{p}}\rceil < \frac{2n}{p}$. Now, as we are counting pairs, and the $n+1$ numbers are unique, we can count $\frac{n}{p}$ slots for the pairs corresponding to p. So, overall we have $\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\cdots+\frac{n}{q}$ such that $q$ is the last prime less than $2n$ (actually $\sqrt{2n}$ should suffice) Now, we have ${n+1 \choose 2 } = \frac{n*(n+1)}{2}$. So, as the above summation is less than $n+1 \choose 2$(every prime after 3 is greater than 2 and there are at most n terms), we must have some pair outside these multiplication tables hence two co-prime numbers among these must exist.

If I understand what you've done correctly, it doesn't work. You can certainly have a lot more than $\frac n2$ pairs which have a factor of $2$ in common: in fact you can have $\binom n2$ since all the even numbers could be in your set.
• So, should my summation change to ${n \choose 2}+{2n/3 \choose 2}+{2n/5 \choose 2}+\cdots+{2n/q \choose 2}$? – bat_of_doom Jul 12 '17 at 9:06
• Yes, that's right. But this is going to be bigger than $\binom{n+1}2$. – Especially Lime Jul 12 '17 at 9:09
• That is, there are enough non-coprime pairs for the number of pairs you need. So you'd need to use the fact that all the pairs between numbers you choose have to be coprime, and this stops you using both of the pairs $(4,6)$ and $(3,9)$, etc. – Especially Lime Jul 12 '17 at 9:14
$n$ numbers can be chosen out of $2n$ numbers with a gap between any two numbers. So by the pigeon hole principle the $(n+1)$th number will be adjacent to one of the $n$ numbers. Hence there is at least one pair that is consecutive hence co-prime.
Partition the set of numbers from $1$ to $2n$ into $n$ subsets $\{ \{2i-1,2i\}: 1\leq i\leq n\}.$ By the Pigeon-Hole Principle, if $n+1$ numbers are chosen from $1,..., 2n$ then for some $i$ the set $\{2i-1,2i\}$ will contain $2$ of them.