Browse · MathNet
PrintMathematica competitions in Croatia
Croatia number theory
Problem
Prove that among any seven squares of positive integers there are two whose difference is divisible by .
Solution
Let the seven squares be where are positive integers.
Consider the possible residues of modulo .
Since can be any integer, modulo depends on modulo .
Let us compute for :
So the possible residues are .
Counting the number of distinct residues: - (for ) - (for ) - (for ) - (for ) - (for ) - (for )
There are only possible residues for squares modulo .
By the pigeonhole principle, among any squares, at least two must have the same residue modulo .
Therefore, their difference is divisible by .
Consider the possible residues of modulo .
Since can be any integer, modulo depends on modulo .
Let us compute for :
| 0 | 0 |
| 1 | 1 |
| 2 | 4 |
| 3 | 9 |
| 4 | 16 |
| 5 | 5 |
| 6 | 16 |
| 7 | 9 |
| 8 | 4 |
| 9 | 1 |
| 10 | 0 |
| 11 | 1 |
| 12 | 4 |
| 13 | 9 |
| 14 | 16 |
| 15 | 5 |
| 16 | 16 |
| 17 | 9 |
| 18 | 4 |
| 19 | 1 |
Counting the number of distinct residues: - (for ) - (for ) - (for ) - (for ) - (for ) - (for )
There are only possible residues for squares modulo .
By the pigeonhole principle, among any squares, at least two must have the same residue modulo .
Therefore, their difference is divisible by .
Techniques
Modular ArithmeticPigeonhole principle