Skip to main content
OlympiadHQ

Browse · MathNet

Print

Mathematica 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 :
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 .

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