Euler Criterion

Detecting Quadratic Residues

Euler criterion gives an efficient way to decide whether an integer is a square modulo an odd prime. Let $p$ be an odd prime and let $a$ be an integer not divisible by $p$. Then $a$ is either a quadratic residue modulo $p$ or a quadratic nonresidue modulo $p$.

The criterion states that this distinction is detected by the power

$$ a^{(p-1)/2}. $$

More precisely,

$$ a^{(p-1)/2}\equiv \begin{cases} 1 \pmod p, & \text{if } a \text{ is a quadratic residue modulo } p,\ -1 \pmod p, & \text{if } a \text{ is a quadratic nonresidue modulo } p. \end{cases} $$

Equivalently, using the Legendre symbol,

$$ a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\pmod p. $$

Statement of the Theorem

Theorem. Let $p$ be an odd prime and let $a\in\mathbb{Z}$ with $p\nmid a$. Then

$$ a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\pmod p. $$

This is Euler criterion.

It turns the problem of solving

$$ x^2\equiv a\pmod p $$

into a modular exponentiation problem.

Proof

The nonzero residue classes modulo $p$ form a multiplicative group

$$ \mathbb{F}_p^\times $$

of order

$$ p-1. $$

By Fermat little theorem,

$$ a^{p-1}\equiv1\pmod p. $$

Therefore

$$ \left(a^{(p-1)/2}\right)^2\equiv1\pmod p. $$

So

$$ a^{(p-1)/2}\equiv1\pmod p $$

or

$$ a^{(p-1)/2}\equiv-1\pmod p. $$

Now suppose $a$ is a quadratic residue modulo $p$. Then there exists an integer $x$ such that

$$ a\equiv x^2\pmod p. $$

Hence

$$ a^{(p-1)/2}\equiv (x^2)^{(p-1)/2}=x^{p-1}\equiv1\pmod p. $$

So quadratic residues give the value $1$.

It remains to see that nonresidues give the value $-1$. Since exactly half of the nonzero residue classes modulo $p$ are quadratic residues, there are

$$ \frac{p-1}{2} $$

quadratic residues. The polynomial

$$ X^{(p-1)/2}-1 $$

has degree $(p-1)/2$, and we have already found $(p-1)/2$ roots, namely the nonzero quadratic residues. Therefore these are all its roots in $\mathbb{F}_p$.

Thus any nonresidue cannot satisfy

$$ a^{(p-1)/2}\equiv1\pmod p. $$

Since the only possible values are $1$ and $-1$, every quadratic nonresidue satisfies

$$ a^{(p-1)/2}\equiv-1\pmod p. $$

This proves the theorem.

Example

Determine whether $5$ is a quadratic residue modulo $11$.

Compute

$$ 5^{(11-1)/2}=5^5. $$

Modulo $11$,

$$ 5^2=25\equiv3, $$

$$ 5^4\equiv3^2=9, $$

so

$$ 5^5\equiv9\cdot5=45\equiv1\pmod{11}. $$

Therefore

$$ \left(\frac{5}{11}\right)=1. $$

Hence $5$ is a quadratic residue modulo $11$. Indeed,

$$ 4^2=16\equiv5\pmod{11}, $$

and also

$$ 7^2=49\equiv5\pmod{11}. $$

Example of a Nonresidue

Determine whether $2$ is a quadratic residue modulo $11$.

Compute

$$ 2^5=32\equiv-1\pmod{11}. $$

Therefore

$$ \left(\frac{2}{11}\right)=-1. $$

So $2$ is a quadratic nonresidue modulo $11$. The congruence

$$ x^2\equiv2\pmod{11} $$

has no solution.

Computational Use

Euler criterion is effective because modular exponentiation can be performed quickly by repeated squaring.

For large primes, checking all squares modulo $p$ would be inefficient. Euler criterion reduces the problem to computing one power modulo $p$.

For example, to test whether $a$ is a quadratic residue modulo a large prime $p$, compute

$$ a^{(p-1)/2}\pmod p. $$

If the result is $1$, then $a$ is a residue. If the result is $p-1$, which represents $-1$, then $a$ is a nonresidue.

This is useful in computational number theory, cryptography, and primality testing.

Relation to Group Theory

Euler criterion reflects the structure of the cyclic group

$$ \mathbb{F}_p^\times. $$

Since this group has order $p-1$, its subgroup of squares has order

$$ \frac{p-1}{2}. $$

The map

$$ x\mapsto x^2 $$

has kernel

$$ {1,-1}, $$

so its image has exactly half of the nonzero elements.

The function

$$ a\mapsto a^{(p-1)/2} $$

is a group homomorphism from

$$ \mathbb{F}_p^\times $$

to

$$ {1,-1}. $$

Its kernel is precisely the subgroup of squares. Thus Euler criterion identifies the quadratic residue character of the finite field.

Conceptual Meaning

Euler criterion translates a solvability question into a power congruence. Instead of asking directly whether

$$ x^2\equiv a\pmod p $$

has a solution, it asks whether $a$ lies in the kernel of the character

$$ a\mapsto a^{(p-1)/2}. $$

This viewpoint prepares the way for quadratic reciprocity, Dirichlet characters, and the use of multiplicative characters in analytic number theory.