Track / Stage 5 / 167 of 400 #1247 of 2444

Problem 1247

AIME late

Number theory Difficulty 5.3 Prove it Austrian Mathematical Olympiad · Austria

For each prime number $p$ , determine the number of residue classes modulo $p$ which can be represented as $a^2 + b^2$ modulo $p$ , where $a$ and $b$ are arbitrary integers.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

All $p$ residue classes.

With $a^2 + 0^2$ we first obtain all quadratic residue classes.
Since not all residue classes are quadratic residues, there is a quadratic residue class $a^2$ that is followed by a quadratic non-residue class, so that $n = a^2 + 1$ is not a quadratic residue and therefore of course $n \neq 0 \pmod p$ .
However, since the product of two quadratic non-residue classes is a quadratic residue class, it follows for each quadratic non-residue class $m$ that $m = nmn/n^2 = (a^2+1)c^2/n^2 \equiv (acn^{-1})^2 + (cn^{-1})^2 \pmod p$ and therefore all quadratic residue classes can also be represented as the sum of two squares.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.