Prove that in any set of $n+2$ ($n > 0$)natural numbers we can find two numbers $a, b$ such, that $2n | (a^2 - b^2)$

Question

Prove that in any set of $n+2$ ($n > 0$)natural numbers we can find two numbers $a, b$ such, that $2n | (a^2 - b^2)$

I found this problem a little bit confusing at first - I asked myself - why $n+2$ and not $n+1$?


$$2n|(a^2-b^2) \iff 2n |(a-b)(a+b) \iff (n|(a-b) \land 2|(a+b)) \lor (n|(a+b) \land 2|(a-b)) $$ Now, we need to somehow show that, given $n+2$ numbers, we can find that the sum or difference of two of them will be divisible by $2$ and the other - divisible by $n$. The options are as follows:
1) The numbers are of the same parity and give the same remainder under division by $n$
2) They are of the same parity and they remainders add up to $n$

How can I ensure that I in fact will find such numbers in my set?

Answer 1

We have to be a little more creative with the Pigeonhole Principle here.

We can consider two cases: $n$ odd and $n$ even.

If $n$ is odd, let's sort the numbers into $\frac{n+1}{2}$ boxes, numbered from $0$ through $\frac{n-1}{2}$: in box #$i$, we place any number whose remainder when divided by $n$ is either $i$ or $n-i$. Since there are more than $n+1$ numbers (this is where the $n+2$ comes in!), some box will contain $3$ numbers. $2$ of them must have the same parity, so choose these as $a$ and $b$; then $a^2 - b^2$ will be even, and the remainder when it is divided by $n$ will be $(\pm i)^2 - (\pm i)^2 = i^2 -i^2 = 0$.

If $n$ is even we can do something similar, though we have to be a little more careful, and consider one special case. We set up the boxes in the same way, numbered from $0$ through $\frac{n}{2}$; this time there are $\frac{n+2}{2}$ boxes. So either every box has exactly $2$ numbers in it, or some box #$i$ has $3$. If some box has $3$, we subdivide those into two boxes, the number which give remainder $i$ and the numbers which give remainder $n-i$. If some box has three numbers, it has two of the same parity, which is your case (1). If some box has two numbers and the other has one, than either the two are of the same parity (your case (1)) or the two are of opposite parities, and one matches the parity of the thrid number (your case (2)). If every box has exactly $2$, then in particular box #$0$ has $2$ numbers divisible by $n$; their difference is divisible by $n$, so it is even, and their sum is divisible by $n$, giving your case (2).

Answer 2

Perhaps a simpler setup is to divide numbers into $n+1$ classes numbered $0,...,n$ with class $i$ containing numbers congruent to $\pm i$ mod $2n$. Pigeonhole implies two numbers $a,b$ in the same class, and then $a\equiv\pm b$ so $a^2\equiv b^2$ mod $2n$.

It doesn't work with $n+1$, for example with $n=3$ if you have $4$ numbers in different classes such as $3,4,5,6$ they will all have different squares mod $6$.