Number Theory • Topic 26

Euler's Criterion

Euler's Criterion provides a direct formula to compute the Legendre symbol using modular exponentiation. It connects the geometric concept of "residues" to algebraic calculation.

Statement

Theorem (Euler's Criterion)

For an odd prime

p

and integer

a

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p)

Since the Legendre symbol is $\pm 1$ , this congruence uniquely determines it.

Special Cases

1. Quadratic Character of -1

Substitute

a = - 1

(\frac{- 1}{p}) \equiv (- 1)^{(p - 1) /2} (mod p)

If $p \equiv 1 (mod 4)$ : exponent is even $⟹ (\frac{- 1}{p}) = 1$ . ( $- 1$ is a residue).
If $p \equiv 3 (mod 4)$ : exponent is odd $⟹ (\frac{- 1}{p}) = - 1$ . ( $- 1$ is a non-residue).

2. Quadratic Character of 2

A standard result derived from Euler's Criterion (using Gauss's Lemma):

(\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8}

$1$ if $p \equiv 1, 7 (mod 8)$ .
$- 1$ if $p \equiv 3, 5 (mod 8)$ .

Practice Problems

Exercise (Problem 1)

Determine if

x^{2} \equiv - 1 (mod 2027)

has a solution. (

2027 \equiv 3 (mod 4)

Exercise (Problem 2)

Use Euler's Criterion to prove the multiplicative property of the Legendre symbol.

Exercise (Problem 3)

Find all primes

p

for which 2 is a quadratic residue.