Quadratic Residues
We can add, subtract, multiply and even
divide modulo
n. The next natural question is about square roots: which
numbers are perfect squares in clock arithmetic? The answer splits the residues into two camps and
opens one of the most beautiful chapters in number theory.
Definition
A number a (coprime to n) is a
quadratic residue modulo n if it is a square — if
x^{2} \equiv a \pmod n has a solution. Otherwise it is a
quadratic non-residue.
Square every residue modulo 7:
1^2\equiv 1,\ \ 2^2\equiv 4,\ \ 3^2\equiv 2,\ \ 4^2\equiv 2,\ \ 5^2\equiv 4,\ \ 6^2\equiv 1.
So the residues are \{1, 2, 4\} and the non-residues are
\{3, 5, 6\} — a clean three-three split.
Exactly half are squares
Modulo an odd prime p, exactly
\tfrac{p-1}{2} of the nonzero residues are quadratic residues, and
the other \tfrac{p-1}{2} are non-residues.
The reason is the pairing x and -x: they
square to the same value, so the p-1 nonzero residues collapse
two-to-one onto \tfrac{p-1}{2} distinct squares. (That is why
1 and 6 \equiv -1 both squared to
1 above.)
A multiplication rule
Residues and non-residues multiply like signs — like + and
-:
\text{R}\cdot\text{R} = \text{R}, \quad \text{R}\cdot\text{N} = \text{N}, \quad \text{N}\cdot\text{N} = \text{R}.
This sign-like behaviour begs for a compact notation that captures it — the
Legendre symbol,
next — and it ultimately governs which numbers have square roots in cryptographic settings.