Squares mod p

Which numbers are perfect squares mod $p$? It sounds like a small question, but it leads to one of the deepest results in elementary number theory. We start by counting, using modular arithmetic and Euclid's lemma from unique factorization.

Definition. Let $p$ be an odd prime and $p \nmid a$. Then $a$ is a quadratic residue mod $p$ if $x^{2} \equiv a \pmod{p}$ has a solution, and a quadratic nonresidue if it does not.

Theorem. Mod an odd prime $p$, exactly $\frac{p - 1}{2}$ of the numbers $1, \dots, p - 1$ are quadratic residues, and each one has exactly two square roots, $x$ and $-x$.

Why it works

$x^{2} \equiv y^{2}$ means $p \mid (x - y)(x + y)$, so by Euclid's lemma $x \equiv y$ or $x \equiv -y$. So squaring sends the $p - 1$ nonzero residues to their squares two at a time: $x$ and $-x$ always land together, and they are different because $p$ is odd ($x \equiv -x$ would mean $p \mid 2x$). That leaves exactly $\frac{p - 1}{2}$ different squares. In practice, square $1, 2, \dots, \frac{p - 1}{2}$; the rest repeat these.

Arrows from $x$ to $x^{2} \bmod 11$. Pairs $x$ and $11 - x$ meet at the same square, so only 5 of the 10 nonzero points are hit: $1, 3, 4, 5, 9$. The hollow points are the nonresidues.

Worked example: All the squares

Find the quadratic residues mod 11.

$1^{2} = 1$, $2^{2} = 4$, $3^{2} = 9$, $4^{2} = 16 \equiv 5$, $5^{2} = 25 \equiv 3$.
The residues are $1, 3, 4, 5, 9$; the nonresidues are $2, 6, 7, 8, 10$. Five of each.

Answer: $\{1, 3, 4, 5, 9\}$.

Worked example: Square roots mod p

Solve $x^{2} \equiv 5 \pmod{11}$, and then $x^{2} \equiv 2 \pmod{11}$.

From the list, $4^{2} \equiv 5$, so $x \equiv 4$ or $x \equiv -4 \equiv 7$. Check: $7^{2} = 49 = 44 + 5$.
$2$ is not on the list, so $x^{2} \equiv 2 \pmod{11}$ has no solution.

Answer: $x \in \{4, 7\}$; no solution.

Worked example: A composite modulus is different

Solve $x^{2} \equiv 1 \pmod{15}$.

Mod 3: $x \equiv \pm 1$. Mod 5: $x \equiv \pm 1$. Each of the four sign choices gives one solution mod 15 by the Chinese Remainder Theorem.
They are $1, 4, 11, 14$. Check: $4^{2} = 16$ and $11^{2} = 121 = 120 + 1$.

Answer: Four solutions: $1, 4, 11, 14$.

Squares multiply like signs: residue times residue is a residue (obviously, $x^{2}y^{2} = (xy)^{2}$), and, less obviously, residue times nonresidue is a nonresidue and nonresidue times nonresidue is a residue. Mod 11: $2 \cdot 6 = 12 \equiv 1$, a residue. The next lesson explains why.

Common mistake

Forgetting that $x$ and $-x$ have the same square, and so expecting $p - 1$ different nonzero squares. Mod 11, $5^{2} = 25 \equiv 3$ and $6^{2} = 36 \equiv 3$ too. Only $\frac{p - 1}{2}$ squares appear, each with exactly two roots, and only when $p$ is prime: mod 15 the number 1 has four square roots.

Key idea

Mod an odd prime $p$, squaring is two-to-one on the nonzero residues: exactly half of them, $\frac{p-1}{2}$, are squares, each with roots $\pm x$.

Squares mod p

Practice

Builds on

Leads to

Sources and further reading