The Legendre Symbol and Euler's Criterion

Listing squares works mod 11, but not mod a prime with 50 digits. Euler found a test that needs only one fast power, and it comes straight from Fermat's theorem.

The Legendre symbol. For an odd prime $p$ and an integer $a$, $$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } p \nmid a \text{ and } a \text{ is a quadratic residue mod } p, \\ -1 & \text{if } a \text{ is a nonresidue mod } p, \\ 0 & \text{if } p \mid a. \end{cases}$$ It looks like a fraction, but it is not division: it is a label, $1$, $-1$ or $0$.

Euler's criterion. For an odd prime $p$, $$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}.$$

Why it works

Suppose $p \nmid a$ and let $b = a^{(p-1)/2}$. Then $b^{2} = a^{p-1} \equiv 1$, so $b \equiv \pm 1$ (only $\pm 1$ square to 1 mod a prime). Which sign? Take a primitive root $g$ and write $a \equiv g^{k}$. The squares are exactly the even powers of $g$. And $b = g^{k(p-1)/2} \equiv 1$ exactly when $p - 1 \mid k\frac{p-1}{2}$, that is, when $k$ is even. So $b \equiv 1$ exactly for the residues.

Mod 11, the column $a^{5}$ is always $1$ or $-1$, and it is $1$ in exactly the rows where $a$ has a square root (1, 3, 4, 5, 9).

Worked example: A residue

Find $\left(\frac{3}{11}\right)$.

$\frac{11 - 1}{2} = 5$, so compute $3^{5} = 243 = 22 \cdot 11 + 1 \equiv 1$.
So $\left(\frac{3}{11}\right) = 1$. Indeed $5^{2} = 25 \equiv 3 \pmod{11}$.

Answer: $1$.

Worked example: A nonresidue

Find $\left(\frac{2}{13}\right)$.

$2^{6} = 64 = 4 \cdot 13 + 12 \equiv 12 \equiv -1 \pmod{13}$.
So $\left(\frac{2}{13}\right) = -1$: 2 is not a square mod 13. (The squares mod 13 are $1, 4, 9, 3, 12, 10$.)

Answer: $-1$.

Multiplicativity. Since $(ab)^{(p-1)/2} = a^{(p-1)/2} b^{(p-1)/2}$, Euler's criterion gives $$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$$ This is the "signs" rule from the last lesson: two nonresidues multiply to a residue.

Worked example: Splitting into factors

Find $\left(\frac{6}{13}\right)$.

$\left(\frac{6}{13}\right) = \left(\frac{2}{13}\right)\left(\frac{3}{13}\right)$.
$\left(\frac{2}{13}\right) = -1$ (above). $3^{6} = 729 = 56 \cdot 13 + 1$, so $\left(\frac{3}{13}\right) = 1$.
So $\left(\frac{6}{13}\right) = -1$, and 6 is not among the squares mod 13.

Answer: $-1$.

Why this matters: deciding whether $a$ is a square by listing squares takes about $\frac{p}{2}$ steps, hopeless for a 50-digit prime. Euler's criterion needs one repeated-squaring computation of $a^{(p-1)/2}$, about 330 multiplications for a 50-digit $p$. It says whether a square root exists, though not what it is. Finding the root takes more work (the Tonelli–Shanks algorithm), and that is left for later.

Common mistake

Reading $\left(\frac{a}{p}\right)$ as the fraction $a \div p$. $\left(\frac{3}{11}\right)$ is not $0.27\ldots$; it is $1$, because 3 is a square mod 11. Every Legendre symbol is $1$, $-1$ or $0$. Euler's power will come out as $1$ or $p - 1$, and $p - 1$ means $-1$.

Key idea

$\left(\frac{a}{p}\right) = \pm 1$ says whether $a$ is a square mod $p$, and Euler's criterion computes it: $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$. The symbol is multiplicative in $a$.

The Legendre Symbol and Euler's Criterion

Practice

Builds on

Leads to

Sources and further reading