# 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.