Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100.

I was thinking about using recurrence, but it seems like pigeonhole may also work. I don’t know where to start.

Answer

Look at your $52$ integers mod $100$. Look at the pairs of additive inverses $(0,0)$, $(1,99)$, $(2,98)$, etc. There are $51$ such pairs. Since we have $52$ integers, two of them must belong to a pair $(x,-x)$. Then $x^2 – (-x)^2 = 0 \pmod{100}$, so that the difference of their squares is divisible by $100$.

Attribution
Source : Link , Question Author : SSS , Answer Author : Dylan Yott

Leave a Comment