Take the 2-minute tour ×

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10. I'm trying to apply the pigeonhole principle, but haven't been able to come up with a convincing argument.

Though similar to this question, I think the difference between the two is enough to warrant a second post.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

$$a\equiv0,\pm1,\pm2,\pm3,\pm4,5\pmod{10}\implies a^2\equiv0,1,4,9,6,5$$ So, there are $6$ in-congruent squares $\pmod{10}$

So, if we choose more than $6$ distinct integers, at least two squares will be congruent $\pmod{10}$

share|improve this answer
Thanks, I think I'm getting it now. –  Isaac Zebulun Burke Dec 5 '13 at 18:44
@IsaacZebulunBurke, nice to hear that –  lab bhattacharjee Dec 5 '13 at 18:45
So we have that there exist $a_i,a_j$ amongst the seven integers such that $a_i^2 \equiv a_j^2 \bmod{10} \Rightarrow a_i^2-a_j^2\equiv 0 \bmod{10} \Rightarrow (a_i+a_j)(a_i-a_j)\equiv 0 \bmod{10} \Rightarrow$ either $(a_i+a_j)$ or $(a_i-a_j)$ is divisible by $10$. –  Isaac Zebulun Burke Dec 5 '13 at 18:55
@IsaacZebulunBurke, observe that $a_i+a_j-(a_i-a_j)=2a_j$ which is even. So, if $a_i+a_j,(a_i-a_j)$ have same parity. Now, if $10$ divides $(a_i+a_j)(a_i−a_j),$ both are even. As $5$ is prime, it must divide on the multiplicands –  lab bhattacharjee Dec 5 '13 at 18:58
So what I wrote previously would not suffice, would it? I'm not sure if I understand your last comment. –  Isaac Zebulun Burke Dec 5 '13 at 19:02

Your Answer


