Maths Olympiad Prep

Library / /29 of 82

Number theory Difficulty 5.3 AIME, harder Prove it Croatia

Prove that among any seven squares of positive integers there are two whose difference is divisible by 2020.

Solution

Let the seven squares be a12,a22,,a72a_1^2, a_2^2, \ldots, a_7^2 where aia_i are positive integers.

Consider the possible residues of a2a^2 modulo 2020.

Since aa can be any integer, a2a^2 modulo 2020 depends on aa modulo 2020.

Let us compute a2mod20a^2 \bmod 20 for a=0,1,,19a = 0, 1, \ldots, 19:

aaa2mod20a^2 \bmod 20
00
11
24
39
416
55
616
79
84
91
100
111
124
139
1416
155
1616
179
184
191

So the possible residues are 0,1,4,5,9,160, 1, 4, 5, 9, 16.

Counting the number of distinct residues:
- 00 (for a0,10(mod20)a \equiv 0, 10 \pmod{20})
- 11 (for a1,9,11,19(mod20)a \equiv 1, 9, 11, 19 \pmod{20})
- 44 (for a2,8,12,18(mod20)a \equiv 2, 8, 12, 18 \pmod{20})
- 55 (for a5,15(mod20)a \equiv 5, 15 \pmod{20})
- 99 (for a3,7,13,17(mod20)a \equiv 3, 7, 13, 17 \pmod{20})
- 1616 (for a4,6,14,16(mod20)a \equiv 4, 6, 14, 16 \pmod{20})

There are only 66 possible residues for squares modulo 2020.

By the pigeonhole principle, among any 77 squares, at least two must have the same residue modulo 2020.

Therefore, their difference is divisible by 2020.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.