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.

• You may think wise to precise that the integers all have to be distinct. Dec 13, 2013 at 14:29
• Dec 13, 2013 at 15:04
• Certainly the result is still true even if the integers aren't distinct! Dec 13, 2013 at 15:32
• @Wolfman: The whole world considers 0 to be divisible by 100, surely? Dec 14, 2013 at 9:30
• @WolfmanJoe Relevant: 0 is an even number. (0 is divisible by 2.) Dec 18, 2013 at 19:45

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$.

• Instead of $(x,-x)$ they might also be $(x,x)$ Dec 12, 2013 at 20:56
• @HagenvonEitzen, however this occurs precisely when $x=-x$, or when $x=0,50$ Dec 12, 2013 at 21:01
• I recognize this solution isn't optimal, but I figured I'd give it because it seemed like the intended method and also has the advantage of not needing to know the number of squares mod $100$. Dec 13, 2013 at 7:08
• This seems to have the advantage that it does not use the factorization of $100$. If you ask the same question modulo $2k$ (instead of modulo $100$), you would get $k+1$ pairs, so $k+2$ integers would certainly be enough. For odd "base", i.e. modulo $(2k+1)$, we also get $k+1$ pairs, and $k+2$ integers suffice again. Dec 13, 2013 at 13:43
• @DylanYott: This will work for any $x = y, y+50$. Jan 16, 2014 at 4:46

Only 23 numbers are needed. There are only $22$ squares mod $100$, so if you have $23$ integers, two must be yield the same square mod $100$. That is, you must have two different values, $a$ and $b$, such that $a^2 \equiv b^2 \pmod {100}$. Hence, $100$ divides $a^2-b^2$.

Here are the $22$ squares : $$0,1,4,9,16,21,24,25,29,36,41,44,49,56,61,64,69,76,81,84,89,96.$$

Added: Note that since there are $22$ squares mod $100$, we can create sets of $22$ integers for which there is no pair with the property that the difference of their squares is divisible by $100$. Hence, the $23$ here is best possible.

Every square is congruent to either $0$ or $1$ modulo $4$. Also, there are $11$ distinct squares modulo $25$. By the Chinese remainder theorem, there are only $2\cdot11=22$ distinct squares modulo $100$. So the $52$ in the problem can be improved to $23$.

• Nice generalization of the technique used above by @Matthew Conroy. Dec 13, 2013 at 2:26
• I was just about to ask how * did you know there are 22 suqares mod 100 Dec 13, 2013 at 5:42
• Yes, thanks for reminding me of this theorem... since I attempted the problem before reading the other answers, I enumerated them and then had to work backward... good thing it wasn't modulo 10000. Dec 13, 2013 at 22:20
• Fascinating how much attention this is getting. For future readers, here is how to quickly count the 11 distinct squares modulo 25: $a^2\equiv b^2$ is the same as $(a-b)(a+b)\equiv0\pmod{25}$. The most trival case is $a\equiv b$, then comes $a+b\equiv 0$, which shows that we need only consider $0,1,\ldots,12$. If neither congruence holds, then both of $a\pm b$ must be divisible by $5$, hence so must both $a$ and $b$. This takes care of the cases 0, 5, and 10, all having the same square 0. The remaining ten will have non-congruent squares. Dec 14, 2013 at 14:17

In 26 integers, by Pigeonhole Principle you have at least two whose difference is zero when divided by 25. In 52 integers you have at least 3 such integers. Pick those three integers. Again, by Pigeonhole, two of them will have the same parity. Let them be $a$ and $b$. Thus $2|(a+b)$ and $2|(a-b)$ as such $4|(a+b)(a-b)$. Since 25|(a+b)(a-b) also and 4 and 25 are relatively prime you have $100|(a^2-b^2)$.

• Nice, but this must not be the intended solution, because it your use of the pigeonhole principle requires only 51 integers.
– bof
Dec 13, 2013 at 7:26

Look at your $52$ integers $\mod 100$. So, the difference of their squares resulting in division by $100$ can be given by $a^2=b^2(\mod 100)$. This will resolute in product of the difference of the numbers and sum of the numbers is divisible by $100$. since, any of $52$ integer numbers are asked, there can be no optimal solution answer for this.

For example:- Look at the pairs of additive inverses $(0,100)$, $(1,99)$, $(2,98)$, etc. There are $51$ such pairs. Since we have $52$ integers, two of them must belong to a pair $(a,−a)$. Then $a^2-(−a)^2=0(\mod 100)$, so that the difference of their squares is divisible by $100$. Likewise, since square of $10$ is $100$, so all the pair of integers with a difference of multiple of $10$ and the numbers whose additive numbers comes resulting in $\mod 10$ will also end up in the difference of squares is divisible by $100$. For example: $(0,10)$, $(10,20)$, $(20,30)$,... etc. Similarly, sum is multiple of $20$ and difference is multiple of $5$ will produce the same result. so, this assumption is proved.

But the following analysis can be further improved by Chinese remainder theorem. There are $11$ distinct squares modulo $25$. By the Chinese remainder theorem, there are only $2\cdot 11=22$ distinct squares modulo $100$. So the $52$ in the problem can be improved to $23$. since, square of $0$'s at unit place ending up in $0$, likewise $1$ in $1$, $2$ in $4$, $3$ in $9$, $4$ in $6$, $5$ in $5$, $6$ in $6$, $7$ in $9$, $8$ in $4$, $9$ in $1$. So, every square is congruent to either $0$ or $1$ or modulo $4$. so, there are only $23$ integers, for which two of the integers will draw the result that difference of their squares is divisible by $100$.

As other people pointed out that even if we use $$23$$ instead of $$52$$, the result holds true,but you cannot always check out the possible remainders by squaring two digit numbers. The problem asks for $$52$$ integers, to simplify the work.

Here is the proof.

List out all the numbers $${a_1}^2,{a_2}^2,{a_3}^2,{a_4}^2 \dots \dots$$ $${a_{52}}^2$$ Now divide the numbers by $$100$$. Now note that dividing a number $$n$$ by $$100$$ is equivalent to extracting the last two digits of the number $$n$$. Now the square of any number ends with 0,1,4,5,6,9 so the possible remainder are $$00,10,20,30 \dots \dots 90;01,11,21,31 \dots \dots 91;02,12,22,32 \dots \dots 92; \dots \dots ;09,19,29,39 \dots \dots 99$$ However any perfect square divisible by $$10$$ is divisible by $$100$$. Hence $$00 ;01,11,21,31 \dots \dots 91;02,12,22,32 \dots \dots 92; \dots \dots ;09,19,29,39 \dots \dots 99$$ are the $$1+10\left(5\right)$$ are $$51$$ possible remainders.Now use Pigeonhole Principle to get two numbers which leave same remainder when divided by 100. Now subtract them.

• Why isn't it possible that remainders be 10,20,30...90? Dec 30, 2018 at 11:35

If the difference $n^2 - m^2$ between two integer squares is an even number, then the numbers, n and m, must either be both odd or both even.

$n^2 - m^2$ must therefore always contain the factor 4 and we only have to consider squares (mod 25). These are the 11 numbers 0, 1, 4, 6, 9, 11, 14, 16, 19, 21 and 24. But 23 numbers must always contain 12 numbers either odd or even.