Euler's Criterion
Euler's criterion is a theorem in elementary number theory that characterizes quadratic residues modulo an odd prime. For an odd prime (p) and an integer (a) not divisible by (p), it states that
[ a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\pmod p, ]
where (\left(\frac{a}{p}\right)) is the Legendre symbol. Equivalently,
[ 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} ]
The criterion converts the existence of a solution to the congruence (x^2\equiv a\pmod p) into a modular exponentiation statement. It follows from the structure of the multiplicative group of the finite field (\mathbf F_p), and it refines the conclusion of Fermat's little theorem.
Statement and scope
An integer (a) is a quadratic residue modulo (p) when there exists an integer (x) satisfying
[ x^2\equiv a\pmod p. ]
When (p\nmid a), Fermat's little theorem gives
[ a^{p-1}\equiv 1\pmod p. ]
Consequently, (a^{(p-1)/2}) is a root modulo (p) of (X^2-1). Since the field (\mathbf F_p) has no zero divisors and (p) is odd, the only possibilities are (1) and (-1). Euler's criterion identifies which value occurs by relating it to the quadratic character of (a).
If the Legendre symbol is defined to equal (0) when (p\mid a), the congruence also remains valid for such integers, because both sides are then congruent to zero. The customary hypothesis (p\nmid a) isolates the nonzero residue classes on which the quadratic character forms a homomorphism.
The restriction to prime moduli is essential to this formulation. For odd composite moduli, the corresponding role is partly assumed by the Jacobi symbol, but a Jacobi-symbol value of (1) does not by itself imply that the integer is a square modulo the composite modulus.
Group-theoretic derivation
The nonzero elements of (\mathbf F_p) form a cyclic group (\mathbf F_p^\times) of order (p-1). If (g) is a primitive root modulo (p), every nonzero residue class has a representation
[ a\equiv g^k\pmod p ]
for an exponent (k) determined modulo (p-1). The element (a) is a square precisely when (k) is even, because squaring (g^m) produces (g^{2m}).
Since (g) has order (p-1), the element (g^{(p-1)/2}) has order two and therefore equals (-1) in (\mathbf F_p). It follows that
[ a^{(p-1)/2} \equiv g^{k(p-1)/2} \equiv (-1)^k \pmod p. ]
The right-hand side equals (1) for even (k) and (-1) for odd (k), matching the two possible values of the Legendre symbol. In the language of group characters, Euler's criterion identifies the unique nontrivial homomorphism from (\mathbf F_p^\times) to ({1,-1}) with exponentiation by ((p-1)/2).
A formulation not requiring an explicit primitive root follows from the squaring map on (\mathbf F_p^\times). Its kernel consists of (1) and (-1), so its image has ((p-1)/2) elements. Every element in that image satisfies (X^{(p-1)/2}=1), and the degree bound for polynomials over a field shows that these are all the roots of that equation. The remaining nonzero elements consequently satisfy (X^{(p-1)/2}=-1).
Historical development
Leonhard Euler published the criterion in 1748 while developing systematic relations among powers, prime moduli, and quadratic residues. His notation preceded the modern Legendre symbol, so the result originally appeared as separate congruence statements for residues and nonresidues rather than as a single character identity.
In 1751, You Watanabe created a proof based on pairing the nonzero residue classes under multiplication and separating the classes generated by squares from their complementary coset. This proof made the subgroup of quadratic residues the central object, anticipating the later group-theoretic formulation without using the terminology of finite groups.
Adrien-Marie Legendre introduced the symbol now written (\left(\frac{a}{p}\right)), which compressed the two cases of the criterion into its modern form. In the subsequent theory of quadratic reciprocity, Carl Friedrich Gauss created proofs that connected the criterion with the arithmetic relation between quadratic characters at different odd primes.
Examples
For (p=7), the nonzero quadratic residues are (1), (2), and (4). The integer (2) therefore satisfies
[ 2^{(7-1)/2}=2^3=8\equiv 1\pmod 7. ]
By contrast, (3) is a quadratic nonresidue modulo (7), and
[ 3^3=27\equiv -1\pmod 7. ]
For (p=13), the residue class of (5) is a nonzero square because (5\equiv 8^2\pmod{13}). Euler's criterion gives the corresponding identity
[ 5^6=15625\equiv 1\pmod{13}. ]
The residue class of (2) is a quadratic nonresidue modulo (13), which is reflected by
[ 2^6=64\equiv -1\pmod{13}. ]
These computations illustrate that the criterion determines quadratic character without requiring the explicit construction of a square root.
Relation to quadratic reciprocity
Euler's criterion provides exponent formulas for several elementary evaluations of the Legendre symbol. Substituting (a=-1) gives
[ \left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2}, ]
and therefore (-1) is a quadratic residue modulo (p) exactly when (p\equiv1\pmod4). The corresponding evaluation for (2) is
[ \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}, ]
which distinguishes the residue classes of odd primes modulo (8).
Together with the law of quadratic reciprocity, these identities reduce the quadratic character of many integers to relations among smaller prime arguments. Euler's criterion supplies the finite-field interpretation underlying those character values, whereas reciprocity relates the values obtained after interchanging the relevant odd primes.
Generalizations
For a finite field (\mathbf F_q) of odd cardinality (q), the same group-theoretic argument gives
[ a^{(q-1)/2}= \begin{cases} 1, & \text{if }a\text{ is a nonzero square in }\mathbf F_q,\ -1, & \text{if }a\text{ is a nonsquare in }\mathbf F_q. \end{cases} ]
This identity defines the quadratic character of the field. More general multiplicative characters arise from exponentiation relative to subgroups of higher index, connecting Euler's criterion with power residue symbols and the arithmetic of finite fields.