Quadratic Residues

This topic asks: "Is $a$ a perfect square modulo $n$?" It leads to the Law of Quadratic Reciprocity, the "Golden Theorem" of number theory.

Definition

Legendre Symbol

• $+1$: if $a$ is a quadratic residue modulo $p$.
• $-1$: if $a$ is a non-residue modulo $p$.
• $0$: if $p\mid a$.

Euler's Criterion

Key Values

1. $-1$ is a residue iff $p\equiv 1(\mathrm{mod}4)$.
2. $2$ is a residue iff $p\equiv 1,7(\mathrm{mod}8)$.

Practice Problems