Find all positive integers for which an integer that can be written as sum of squares of integers with each of them is divisible by , can also be expressed as sum of squares of integers with none of them is divisible by .
Solution
The answer is all positive integers except , and .
Let us call a positive integer *good* if it satisfies the condition given in the problem. We first show that if is good, so is any multiple of .
Let and be integers such that for all . Then since for all and is good, there exist integers such that
for all and for all . Therefore we obtain that
and for all .
Lemma: Let be a positive odd integer and be integers with at least one of them is not divisible by . Then there exist integers such that none of them is divisible by and
*Proof:* Without loss of generality we may assume that . Let . If , then replace by . As and is odd, and hence we may assume that . Then by the following identity
letting for all works.
For a positive odd integer , if a positive integer is sum of squares of integers with each of them is divisible by , then there exist integers and a positive integer such that and for some . Applying the lemma times we can find integers such that and for all .
Next we show that is good. Let be positive integer which is sum of squares of integers with each of them is divisible by . Then , hence and for some integers by Lagrange's four-square theorem. Note that and the only way to get as sum of four quadratic residues in (mod ) is . Therefore, for all .
Finally, we observe that is a counterexample for and we are done.