Skip to content

Euler Criterion

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

number-theory book chatgpt

Detecting Quadratic Residues

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

The criterion states that this distinction is detected by the power

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

More precisely,

a(p−1)/2≡{1(modp),if a is a quadratic residue modulo p,−1(modp),if a is a quadratic nonresidue modulo p. 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≡(ap)(modp). a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\pmod p.

Statement of the Theorem

Theorem. Let pp be an odd prime and let a∈Za\in\mathbb{Z} with p∤ap\nmid a. Then

a(p−1)/2≡(ap)(modp). a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\pmod p.

This is Euler criterion.

It turns the problem of solving

x2≡a(modp) x^2\equiv a\pmod p

into a modular exponentiation problem.

Proof

The nonzero residue classes modulo pp form a multiplicative group

Fp× \mathbb{F}_p^\times

of order

p−1. p-1.

By Fermat little theorem,

ap−1≡1(modp). a^{p-1}\equiv1\pmod p.

Therefore

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

So

a(p−1)/2≡1(modp) a^{(p-1)/2}\equiv1\pmod p

or

a(p−1)/2≡−1(modp). a^{(p-1)/2}\equiv-1\pmod p.

Now suppose aa is a quadratic residue modulo pp. Then there exists an integer xx such that

a≡x2(modp). a\equiv x^2\pmod p.

Hence

a(p−1)/2≡(x2)(p−1)/2=xp−1≡1(modp). a^{(p-1)/2}\equiv (x^2)^{(p-1)/2}=x^{p-1}\equiv1\pmod p.

So quadratic residues give the value 11.

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

p−12 \frac{p-1}{2}

quadratic residues. The polynomial

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

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

Thus any nonresidue cannot satisfy

a(p−1)/2≡1(modp). a^{(p-1)/2}\equiv1\pmod p.

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

a(p−1)/2≡−1(modp). a^{(p-1)/2}\equiv-1\pmod p.

This proves the theorem.

Example

Determine whether 55 is a quadratic residue modulo 1111.

Compute

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

Modulo 1111,

52=25≡3, 5^2=25\equiv3, 54≡32=9, 5^4\equiv3^2=9,

so

55≡9⋅5=45≡1(mod11). 5^5\equiv9\cdot5=45\equiv1\pmod{11}.

Therefore

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

Hence 55 is a quadratic residue modulo 1111. Indeed,

42=16≡5(mod11), 4^2=16\equiv5\pmod{11},

and also

72=49≡5(mod11). 7^2=49\equiv5\pmod{11}.

Example of a Nonresidue

Determine whether 22 is a quadratic residue modulo 1111.

Compute

25=32≡−1(mod11). 2^5=32\equiv-1\pmod{11}.

Therefore

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

So 22 is a quadratic nonresidue modulo 1111. The congruence

x2≡2(mod11) 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 pp would be inefficient. Euler criterion reduces the problem to computing one power modulo pp.

For example, to test whether aa is a quadratic residue modulo a large prime pp, compute

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

If the result is 11, then aa is a residue. If the result is p−1p-1, which represents −1-1, then aa 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

Fp×. \mathbb{F}_p^\times.

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

p−12. \frac{p-1}{2}.

The map

x↦x2 x\mapsto x^2

has kernel

{1,−1}, \{1,-1\},

so its image has exactly half of the nonzero elements.

The function

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

is a group homomorphism from

Fp× \mathbb{F}_p^\times

to

{1,−1}. \{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

x2≡a(modp) x^2\equiv a\pmod p

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

a↦a(p−1)/2. 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.