Euler's Criterion

Which nonzero remainders modulo a prime pp are perfect squares? How can we decide this quickly without listing all squares? This question — quadratic residuosity — sits at the heart of classical number theory. It reappears constantly in modern applications. Given a prime pp and an integer aa not divisible by pp, we want a fast test. We need to know whether x2≡a(modp)x^2 \equiv a \pmod p has a solution. This should avoid brute-force searching over all xx from 11 to p−1p-1. Euler's Criterion answers this with a single modular exponentiation. aa is a quadratic residue mod pp exactly when a(p−1)/2≡1(modp)a^{(p-1)/2} \equiv 1 \pmod p. This is remarkable. It converts a search problem (does some xx square to aa?) into a computation problem (raise aa to a fixed power). The criterion is the engine behind the Legendre Symbol's multiplicativity. It also drives fast primality-adjacent tests. And it underlies the entire machinery of Quadratic Reciprocity that follows it. The big picture is this: Fermat's Little Theorem tells us ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p for any aa coprime to pp. Euler's Criterion refines this. It shows that the "square root" of that statement, a(p−1)/2a^{(p-1)/2}, already carries full information. This information tells us whether aa is a square modulo pp. It can only be +1+1 or −1-1 modulo pp, and it tells you which. This single fact is the bridge between two worlds. One is the purely group-theoretic structure of (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times. The other is the classical, symbol-based language of quadratic residues. This article gives a complete, self-contained proof of Euler's Criterion. It builds from Fermat's Little Theorem and elementary properties of finite fields. It then uses the criterion to compute (−1/p)(-1/p) in closed form. This determines exactly which primes have −1-1 as a quadratic residue. This is the first of the "supplementary laws." It is also a direct stepping stone toward Gauss's Lemma and the full law of Quadratic Reciprocity.

Key takeaways
  • Euler's Criterion states (ap)≡a(p−1)/2(modp)\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p for odd prime pp and gcd⁡(a,p)=1\gcd(a,p)=1.
  • It converts the question "is aa a square mod pp?" into a single fast modular exponentiation.
  • The proof rests on Fermat's Little Theorem and the fact that a polynomial of degree dd has at most dd roots mod a prime.
  • As a corollary, (−1/p)=1(-1/p) = 1 iff p≡1(mod4)p \equiv 1 \pmod 4, and (−1/p)=−1(-1/p) = -1 iff p≡3(mod4)p \equiv 3 \pmod 4.
  • The criterion also gives a clean, computational proof that the Legendre symbol is completely multiplicative in its top argument.
  • It is the direct ancestor of Gauss's Lemma and the launching point for Quadratic Reciprocity.
  • Key idea: the value a(p−1)/2  pa^{(p-1)/2} \bmod p is forced to be ±1\pm 1, and it is +1+1 exactly when aa is a square.

Where this lives today

Euler's Criterion is the computational backbone of the Tonelli–Shanks algorithm for computing square roots modulo a prime, which is used throughout elliptic-curve cryptography to decompress compressed point representations. In cryptographic protocol design, testing quadratic residuosity via fast exponentiation (rather than brute-force search) is essential when primes have hundreds of digits, since it runs in polynomial time via repeated squaring while brute force is exponential. The criterion also underlies the Solovay–Strassen primality test, a randomized algorithm predating the more common Miller–Rabin test, which checks whether a(n−1)/2a^{(n-1)/2} agrees with the Jacobi symbol (an)\left(\frac{a}{n}\right) to probabilistically detect compositeness. In pure mathematics, it is the direct stepping stone to Gauss's Lemma and the full Quadratic Reciprocity law, and its generalization to kk-th power residues (via a(p−1)/k  pa^{(p-1)/k} \bmod p in cyclic groups (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times) appears in the study of cyclotomic fields and Gauss and Jacobi sums. In coding theory and combinatorial design, quadratic residues mod pp (whose recognition relies on this criterion) are used to build Paley graphs and quadratic-residue difference sets.

Ask the tutor: How does Euler's Criterion combine with Gauss's Lemma to prove the full law of Quadratic Reciprocity?

DefinitionQuadratic residue and the Legendre symbol

Let pp be an odd prime and let aa be an integer with p∤ap \nmid a. We say aa is a quadratic residue modulo pp if the congruence

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

has a solution x∈Zx \in \mathbb{Z}; otherwise aa is a quadratic nonresidue. The Legendre symbol is defined by

(ap)={1if a is a quadratic residue mod p,−1if a is a quadratic nonresidue mod p,0if p∣a.\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue mod } p, \\ -1 & \text{if } a \text{ is a quadratic nonresidue mod } p, \\ 0 & \text{if } p \mid a. \end{cases}

When p∤ap\nmid a, the symbol is often extended by declaring it depends only on a  pa \bmod p, since x2≡a(modp)x^2\equiv a\pmod p is solvable iff x2≡a′(modp)x^2 \equiv a' \pmod p is solvable for any a′≡a(modp)a'\equiv a \pmod p.

Intuition

Think of the nonzero residues 1,2,…,p−11, 2, \dots, p-1 modulo pp as forming a group under multiplication, (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times, which has order p−1p-1. Squaring is a group homomorphism from this group to itself, x↦x2x \mapsto x^2. Its image is exactly the set of quadratic residues. Because squaring is "2-to-1" (each nonzero square has exactly two square roots, xx and −x-x, which are distinct since pp is odd), the image — the quadratic residues — has size exactly (p−1)/2(p-1)/2. So half the nonzero residues are squares and half are not. Euler's Criterion gives an algebraic litmus test distinguishing the two halves. Raise aa to the power (p−1)/2(p-1)/2: Fermat's Little Theorem guarantees ap−1≡1a^{p-1}\equiv 1, so a(p−1)/2a^{(p-1)/2} is a square root of 11 modulo pp, forcing it to be ±1\pm 1. The claim is that it lands on +1+1 precisely for the residues, and −1-1 precisely for the nonresidues. Picture the nonzero residues mod pp split into two equal camps by the exponentiation map a↦a(p−1)/2a \mapsto a^{(p-1)/2}; the criterion says this split coincides exactly with the residue/nonresidue split.

Figure
The squaring map mod p=13p=13 sends 12 nonzero residues onto 6 quadratic residues, each hit twice
Squaring map mod p = 13: domain (top) to image (bottom) 1 2 3 4 5 6 7 8 9 10 11 12 1 3 4 9 10 12 quadratic residues mod 13 (each has two preimages)

The central theorem

TheoremEuler's Criterion

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

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

That is, a(p−1)/2≡1(modp)a^{(p-1)/2} \equiv 1 \pmod p if aa is a quadratic residue mod pp, and a(p−1)/2≡−1(modp)a^{(p-1)/2} \equiv -1 \pmod p if aa is a quadratic nonresidue mod pp.

LemmaA polynomial congruence has few roots

Let pp be prime and let f(x)=cnxn+⋯+c1x+c0f(x) = c_n x^n + \cdots + c_1 x + c_0 be a polynomial with integer coefficients such that p∤cnp \nmid c_n (so ff has degree exactly nn modulo pp). Then the congruence f(x)≡0(modp)f(x) \equiv 0 \pmod p has at most nn incongruent solutions modulo pp.

Proof

We argue by strong induction on nn, using polynomial division modulo a prime, i.e. working in the field Z/pZ\mathbb{Z}/p\mathbb{Z} where every nonzero element is invertible. Base case n=0n=0. Then f(x)=c0f(x)=c_0 with p∤c0p\nmid c_0, so f(x)≡0(modp)f(x)\equiv 0\pmod p never holds; there are 0≤n0 \le n solutions. Inductive step. Suppose the lemma holds for all degrees less than nn, and let ff have degree nn with p∤cnp \nmid c_n. If f(x)≡0(modp)f(x)\equiv 0\pmod p has no solutions, then trivially it has at most nn solutions and we are done. Otherwise let rr be a solution: f(r)≡0(modp)f(r) \equiv 0 \pmod p. Perform polynomial division with remainder over the rationals (or directly with integer coefficients, since we divide by the monic-after-scaling factor x−rx-r): there exist integers-coefficients polynomial q(x)q(x) of degree n−1n-1 and a constant RR such that

f(x)=(x−r)q(x)+Rf(x) = (x-r)q(x) + R

identically as polynomials. Substituting x=rx=r gives f(r)=Rf(r) = R, so R=f(r)≡0(modp)R = f(r) \equiv 0 \pmod p, hence

f(x)≡(x−r)q(x)(modp)f(x) \equiv (x-r) q(x) \pmod p

as a congruence of polynomials (i.e. all coefficients agree mod pp), where q(x)q(x) has leading coefficient equal to cnc_n (division by the monic linear factor x−rx - r does not change the leading coefficient), so p∤p \nmid (leading coefficient of qq) and qq has degree exactly n−1n-1 modulo pp. Now suppose ss is any solution of f(x)≡0(modp)f(x)\equiv 0 \pmod p with s≢r(modp)s \not\equiv r \pmod p. Then

0≡f(s)≡(s−r)q(s)(modp).0 \equiv f(s) \equiv (s-r)q(s) \pmod p.

Since pp is prime, Z/pZ\mathbb{Z}/p\mathbb{Z} has no zero divisors: if p∣(s−r)q(s)p \mid (s-r)q(s) then p∣(s−r)p \mid (s-r) or p∣q(s)p \mid q(s). We assumed s≢rs \not\equiv r, i.e. p∤(s−r)p \nmid (s-r), so we must have p∣q(s)p \mid q(s), i.e. q(s)≡0(modp)q(s) \equiv 0 \pmod p. Thus every solution of f(x)≡0(modp)f(x)\equiv 0\pmod p other than rr (mod pp) is a solution of q(x)≡0(modp)q(x)\equiv 0 \pmod p. By the inductive hypothesis, qq has at most n−1n-1 incongruent roots mod pp. Adding back rr itself, ff has at most n−1+1=nn-1+1 = n incongruent roots mod pp. This completes the induction.

∎
Proof

Proof of Euler's Criterion. We use Fermat's Little Theorem, the root-counting lemma just proved, and basic group theory of (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times.

Step 1: a(p−1)/2≡±1(modp)a^{(p-1)/2} \equiv \pm 1 \pmod p. By Fermat's Little Theorem, since p∤ap \nmid a,

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

Write m=(p−1)/2m = (p-1)/2, an integer since pp is odd. Then

(am−1)(am+1)=a2m−1=ap−1−1≡0(modp).\left(a^m - 1\right)\left(a^m+1\right) = a^{2m} - 1 = a^{p-1}-1 \equiv 0 \pmod p.

Since pp is prime, Z/pZ\mathbb{Z}/p\mathbb{Z} has no zero divisors, so p∣(am−1)p \mid (a^m-1) or p∣(am+1)p \mid (a^m+1); that is,

a(p−1)/2≡1(modp)ora(p−1)/2≡−1(modp),a^{(p-1)/2} \equiv 1 \pmod p \quad\text{or}\quad a^{(p-1)/2}\equiv -1 \pmod p,

and (since pp is odd, 1≢−1(modp)1 \not\equiv -1 \pmod p) exactly one of these holds for each aa.

Step 2: If aa is a quadratic residue, then a(p−1)/2≡1(modp)a^{(p-1)/2}\equiv 1 \pmod p. Suppose a≡x2(modp)a \equiv x^2 \pmod p for some xx with p∤xp \nmid x (note p∤ap\nmid a forces p∤xp \nmid x). Then by Fermat's Little Theorem applied to xx,

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} \equiv 1 \pmod p.

Step 3: Exactly (p−1)/2(p-1)/2 of the residues 1,…,p−11,\dots,p-1 are quadratic residues. Consider the squaring map σ:{1,…,p−1}→{1,…,p−1}\sigma : \{1,\dots,p-1\} \to \{1,\dots,p-1\}, σ(x)=x2  p\sigma(x) = x^2 \bmod p. Its image is precisely the set of quadratic residues (nonzero, since p∤ap\nmid a). For x,y∈{1,…,p−1}x,y \in \{1,\dots,p-1\},

x2≡y2(modp)  ⟺  p∣(x−y)(x+y)  ⟺  x≡y or x≡−y(modp).x^2 \equiv y^2 \pmod p \iff p \mid (x-y)(x+y) \iff x \equiv y \text{ or } x \equiv -y \pmod p.

Since 1≤x,y≤p−11 \le x,y \le p-1 and pp is odd, x≡−y(modp)x \equiv -y \pmod p and x≡y(modp)x \equiv y \pmod p cannot both hold unless x=yx=y and 2x≡02x \equiv 0, impossible for 1≤x≤p−11\le x \le p-1 odd pp unless... more directly: for fixed xx, the two solutions y=xy=x and y=p−xy = p - x of y2≡x2y^2\equiv x^2 are distinct because x≠p−xx \ne p-x (as pp is odd, 2x≠p2x \ne p for integer xx). Hence σ\sigma is exactly 2-to-1 onto its image, so

∣{quadratic residues mod p}∣=p−12.|\{\text{quadratic residues mod } p\}| = \frac{p-1}{2}.

Step 4: The count of solutions to a(p−1)/2≡1a^{(p-1)/2}\equiv 1 is at most (p−1)/2(p-1)/2. By the root-counting Lemma applied to f(x)=x(p−1)/2−1f(x) = x^{(p-1)/2} - 1, which has degree (p−1)/2(p-1)/2 and leading coefficient 11 (so p∤1p \nmid 1), the congruence

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

has at most (p−1)/2(p-1)/2 solutions among x∈{1,…,p−1}x \in \{1,\dots,p-1\}.

Step 5: Conclusion by counting. By Step 2, every quadratic residue aa satisfies a(p−1)/2≡1a^{(p-1)/2}\equiv 1; by Step 3 there are exactly (p−1)/2(p-1)/2 quadratic residues. So the congruence x(p−1)/2≡1(modp)x^{(p-1)/2}\equiv 1 \pmod p has at least (p−1)/2(p-1)/2 solutions (namely, all the quadratic residues, which are distinct mod pp). By Step 4 it has at most (p−1)/2(p-1)/2 solutions. Hence it has exactly (p−1)/2(p-1)/2 solutions, and these must be precisely the quadratic residues — no nonresidue can also satisfy a(p−1)/2≡1a^{(p-1)/2}\equiv 1, since that would give more than (p−1)/2(p-1)/2 solutions, contradicting Step 4. Therefore for a quadratic residue aa, a(p−1)/2≡1≡(ap)(modp)a^{(p-1)/2}\equiv 1 \equiv \left(\frac{a}{p}\right) \pmod p, and for a quadratic nonresidue aa, by Step 1 (exactly one of ±1\pm1 occurs) and the exclusion just proved, a(p−1)/2≡−1≡(ap)(modp)a^{(p-1)/2} \equiv -1 \equiv \left(\frac{a}{p}\right)\pmod p. In both cases (ap)≡a(p−1)/2(modp)\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p, as claimed. ■\blacksquare

∎
CorollaryMultiplicativity of the Legendre symbol

For odd prime pp and integers a,ba,b with p∤abp \nmid ab,

(abp)=(ap)(bp).\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
Proof

By Euler's Criterion,

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

Both sides of (abp)=(ap)(bp)\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) (as an equation, not just a congruence) lie in {1,−1}\{1,-1\}, and two elements of {1,−1}\{1,-1\} that are congruent mod pp (for p>2p>2, so p∤2p \nmid 2) must be equal, since 1≢−1(modp)1 \not\equiv -1 \pmod p. Hence the congruence upgrades to an honest equality. ■\blacksquare

∎
CorollaryThe value of (−1/p)(-1/p): first supplementary law

For every odd prime pp,

(−1p)={1if p≡1(mod4),−1if p≡3(mod4).\left(\frac{-1}{p}\right) = \begin{cases} 1 & \text{if } p \equiv 1 \pmod 4,\\ -1 & \text{if } p \equiv 3 \pmod 4. \end{cases}

Equivalently, (−1p)=(−1)(p−1)/2\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}.

Proof

Apply Euler's Criterion with a=−1a=-1 (valid since p∤−1p \nmid -1 for any prime pp):

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

The right side is exactly ±1\pm 1 (an honest integer, not just a residue class), and the left side is also exactly ±1\pm1. Since pp is odd, 1≢−1(modp)1 \not\equiv -1 \pmod p, so two values in {1,−1}\{1,-1\} congruent mod pp must be equal:

(−1p)=(−1)(p−1)/2.\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}.

Now determine the parity of (p−1)/2(p-1)/2 from p  4p \bmod 4. Write p=4k+1p = 4k+1 or p=4k+3p=4k+3 (these are the only options for an odd prime). If p=4k+1p = 4k+1, then (p−1)/2=2k(p-1)/2 = 2k, which is even, so (−1)(p−1)/2=1(-1)^{(p-1)/2} = 1. If p=4k+3p = 4k+3, then (p−1)/2=2k+1(p-1)/2 = 2k+1, which is odd, so (−1)(p−1)/2=−1(-1)^{(p-1)/2} = -1. This exactly matches the two cases p≡1(mod4)p\equiv 1\pmod 4 and p≡3(mod4)p \equiv 3 \pmod 4, completing the proof. ■\blacksquare

∎

Worked examples

Example 1: Deciding quadratic residuosity via direct exponentiation, p=23p=23, a=15a=15. We test whether x2≡15(mod23)x^2 \equiv 15 \pmod{23} has a solution, using Euler's Criterion with exponent (p−1)/2=11(p-1)/2 = 11. Compute 1511  2315^{11} \bmod 23 by repeated squaring.

151≡15,152=225≡225−9⋅23=225−207=18,154≡182=324≡324−14⋅23=324−322=2.15^1 \equiv 15,\quad 15^2 = 225 \equiv 225 - 9\cdot23 = 225-207=18,\quad 15^4 \equiv 18^2=324 \equiv 324-14\cdot23=324-322=2.
158≡22=4(mod23).15^8 \equiv 2^2 = 4 \pmod{23}.

Now 11=8+2+111 = 8+2+1, so

1511≡158⋅152⋅151≡4⋅18⋅15(mod23).15^{11} \equiv 15^8 \cdot 15^2 \cdot 15^1 \equiv 4 \cdot 18 \cdot 15 \pmod{23}.

Compute 4⋅18=72≡72−3⋅23=72−69=34\cdot 18 = 72 \equiv 72 - 3\cdot23 = 72-69=3. Then 3⋅15=45≡45−23=22≡−1(mod23)3\cdot 15 = 45 \equiv 45-23=22 \equiv -1 \pmod{23}. So 1511≡−1(mod23)15^{11}\equiv -1 \pmod{23}, and by Euler's Criterion (1523)=−1\left(\frac{15}{23}\right) = -1: 15 is a quadratic nonresidue mod 23. As a sanity check by brute force, the quadratic residues mod 23 are the squares of 1,…,111,\dots,11: 1,4,9,16,2(25),13(36),3(49),18(64),12(81),8(100),6(121)1,4,9,16,2(25),13(36),3(49),18(64),12(81),8(100),6(121), giving the set {1,2,3,4,6,8,9,12,13,16,18}\{1,2,3,4,6,8,9,12,13,16,18\} — indeed 1515 is absent, confirming the computation.

Example 2: Using multiplicativity plus (−1/p)(-1/p) to shortcut a computation, p=31p = 31, a=−7a = -7. We want (−731)\left(\frac{-7}{31}\right). First, 31=4⋅7+331 = 4\cdot7+3, so 31≡3(mod4)31 \equiv 3 \pmod 4, and by the corollary (−131)=−1\left(\frac{-1}{31}\right) = -1. By multiplicativity (Corollary above),

(−731)=(−131)(731)=−(731).\left(\frac{-7}{31}\right) = \left(\frac{-1}{31}\right)\left(\frac{7}{31}\right) = -\left(\frac{7}{31}\right).

We compute (731)\left(\frac{7}{31}\right) directly via Euler's Criterion, exponent (31−1)/2=15(31-1)/2=15. Repeated squaring mod 3131:

71≡7,72=49≡49−31=18,74≡182=324≡324−10⋅31=324−310=14.7^1 \equiv 7,\quad 7^2 = 49 \equiv 49-31=18,\quad 7^4 \equiv 18^2 = 324 \equiv 324 - 10\cdot31 = 324-310=14.
78≡142=196≡196−6⋅31=196−186=10.7^8 \equiv 14^2 = 196 \equiv 196 - 6\cdot31 = 196-186=10.

Since 15=8+4+2+115 = 8+4+2+1,

715≡78⋅74⋅72⋅71≡10⋅14⋅18⋅7(mod31).7^{15} \equiv 7^8\cdot 7^4\cdot 7^2 \cdot 7^1 \equiv 10\cdot 14\cdot 18\cdot 7 \pmod{31}.

Compute stepwise: 10⋅14=140≡140−4⋅31=140−124=1610\cdot14=140 \equiv 140-4\cdot31=140-124=16. Then 16⋅18=288≡288−9⋅31=288−279=916\cdot18=288 \equiv 288-9\cdot31=288-279=9. Then 9⋅7=63≡63−2⋅31=19\cdot 7=63\equiv 63-2\cdot31=1. So 715≡1(mod31)7^{15}\equiv 1\pmod{31}, giving (731)=1\left(\frac{7}{31}\right)=1. Therefore

(−731)=−1⋅1=−1,\left(\frac{-7}{31}\right) = -1 \cdot 1 = -1,

so −7-7 is a quadratic nonresidue mod 3131. (Check of the sub-claim: 77 is a QR mod 3131 because 102=100≡100−93=7(mod31)10^2 = 100 \equiv 100-93=7\pmod{31}, confirming (731)=1\left(\frac{7}{31}\right)=1 independently.)

CounterexampleWhy pp must be prime

Euler's Criterion is false, and the underlying root-counting lemma fails, if pp is replaced by a composite modulus. Take n=8n = 8 (not prime) and a=1a = 1, with exponent (n−1)/2(n-1)/2 not even an integer — already the statement doesn't parse — so instead compare against the more informative failure at n=15n=15, testing a=4a=4, a genuine square mod 1515 (22=42^2=4), with the "expected" exponent (n−1)/2=7(n-1)/2 = 7 (using the same formula naively). Compute 47  154^7 \bmod 15. Since 42=16≡1(mod15)4^2=16\equiv 1\pmod{15}, we get 47=(42)3⋅4≡13⋅4=4(mod15)4^7 = (4^2)^3\cdot 4 \equiv 1^3\cdot 4 = 4 \pmod{15}, which is not ±1(mod15)\pm1 \pmod {15} at all. The clean dichotomy "a(n−1)/2≡±1a^{(n-1)/2}\equiv \pm1" simply breaks: (Z/15Z)×(\mathbb{Z}/15\mathbb{Z})^\times is not cyclic (it's Z/2×Z/4\mathbb{Z}/2 \times \mathbb{Z}/4), Fermat's Little Theorem itself fails for composite moduli in this form, and the root-counting lemma (a polynomial of degree dd has at most dd roots) also fails: the congruence x2≡1(mod15)x^2 \equiv 1 \pmod{15} has four solutions, x≡1,4,11,14(mod15)x \equiv 1,4,11,14 \pmod{15}, exceeding the degree 22. This is precisely because Z/15Z\mathbb{Z}/15\mathbb{Z} has zero divisors (3⋅5≡03\cdot5\equiv0 despite neither factor being 00), so the key step "p∣uv⇒p∣up\mid uv \Rightarrow p\mid u or p∣vp\mid v" used in both the lemma and the main proof is simply unavailable. Primality of the modulus is not a decorative hypothesis — it is exactly what makes the zero-divisor-free argument, and hence the entire proof, go through.

Scope, edge cases & common traps

SituationWhat happensWhy
p=2p=2Euler's Criterion as stated does not apply(p−1)/2(p-1)/2 is not well-defined as an exponent giving ±1\pm1 distinctness; every unit mod 22 is 11, the theory is degenerate
p∣ap \mid aLegendre symbol is defined to be 00, and a(p−1)/2≡0a^{(p-1)/2}\equiv 0 tooConsistent extension, but this case is excluded from the theorem's hypotheses and should be checked separately
Composite modulus nnCriterion generally false(Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times need not be cyclic and has zero divisors in Z/nZ\mathbb{Z}/n\mathbb{Z}; see counterexample above
Computing by hand for large ppNever expand a(p−1)/2a^{(p-1)/2} literallyUse repeated squaring (fast exponentiation); this is what makes the criterion computationally useful
Congruence vs. equality(ap)≡a(p−1)/2(modp)\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p is a congruenceIt upgrades to true equality only because both sides lie in {1,−1,0}\{1,-1,0\} and p>2p>2 separates 11 from −1-1

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered
LE
Leonhard Euler
1707–1783 · 18th-century mathematical analysis and number theory, Basel/Berlin/St. Petersburg

Euler was the most prolific mathematician of the eighteenth century, contributing foundational work across analysis, mechanics, graph theory, and number theory. In number theory he studied quadratic and higher residues extensively, proved special cases of what would become quadratic reciprocity, and developed criteria — including the one bearing his name here — for testing residuosity using exponentiation, well before the group-theoretic language of finite fields existed to streamline the proof. His empirical and computational approach to conjectures in this area anticipated the general reciprocity law that Gauss would later prove completely.

History
- 1740s: Euler begins investigating patterns in quadratic residues and power residues while corresponding with Goldbach.
- 1755–1760s: Euler states and uses the criterion a(p−1)/2≡±1(modp)a^{(p-1)/2}\equiv \pm 1\pmod p as a residuosity test in his number-theoretic writings.
- 1785: Legendre introduces the symbol (ap)\left(\frac{a}{p}\right), giving Euler's criterion its now-standard notation.
- 1796–1801: Gauss gives the first complete proof of quadratic reciprocity in Disquisitiones Arithmeticae, building on Euler's criterion and his own Gauss's Lemma.
- 19th–20th centuries: Euler's Criterion becomes a standard tool in algorithmic number theory, generalized to residue tests of higher power via the analogous "power residue criterion" in cyclic groups.
Does Euler's Criterion tell you the actual square root xx, not just whether one exists?

No — it only decides existence, not the value. Euler's Criterion computes a(p−1)/2  pa^{(p-1)/2} \bmod p and checks whether this equals 11 or −1-1; it never touches an explicit xx with x2≡ax^2\equiv a. Finding xx explicitly is a separate, harder computational problem, solved for example by the Tonelli–Shanks algorithm (which in fact uses Euler's Criterion as a subroutine to guide its search). For primes p≡3(mod4)p \equiv 3\pmod4, there is a simple closed form x≡±a(p+1)/4(modp)x \equiv \pm a^{(p+1)/4}\pmod p once you already know aa is a residue, but this shortcut does not generalize to all primes, which is why a full square-root algorithm is more delicate than the residuosity test itself.

Can Euler's Criterion be extended to prime powers or composite moduli?

Not directly in the same clean form, though analogues exist. The proof relies crucially on Z/pZ\mathbb{Z}/p\mathbb{Z} being a field, so that Fermat's Little Theorem holds and polynomials have boundedly many roots. For prime powers pkp^k one can use Hensel lifting to relate residuosity mod pkp^k back to residuosity mod pp, but this requires separate lifting arguments, not a direct analogue of the criterion itself. For general composite nn, one instead works with the Jacobi symbol, a formal extension of the Legendre symbol satisfying reciprocity-like formulas, but the Jacobi symbol being 11 no longer implies aa is actually a quadratic residue mod nn — this asymmetry is exactly what the Solovay–Strassen primality test exploits.

How is Euler's Criterion related to Gauss's Lemma?

Gauss's Lemma is an independent, more geometric criterion for the Legendre symbol, counting how many of the least positive residues of a,2a,…,p−12aa, 2a, \dots, \frac{p-1}{2}a modulo pp exceed p/2p/2; the parity of that count gives (ap)\left(\frac{a}{p}\right). Historically and pedagogically, Gauss's Lemma is often proved independently of Euler's Criterion and then used, together with a clever lattice-point counting argument, to prove full Quadratic Reciprocity. Euler's Criterion and Gauss's Lemma both compute the same object, the Legendre symbol, but via different combinatorial routes — one via a single exponentiation, the other via a sign-counting argument on a set of representative residues.

Why can't a(p−1)/2a^{(p-1)/2} be, say, 22 modulo pp?

Because a(p−1)/2a^{(p-1)/2} is forced by Fermat's Little Theorem to be a square root of 11 modulo pp: squaring it gives ap−1≡1(modp)a^{p-1}\equiv1\pmod p. In the field Z/pZ\mathbb{Z}/p\mathbb{Z}, the equation y2≡1y^2 \equiv 1 has at most two roots (by the root-counting lemma with d=2d=2), and 11 and −1-1 are visibly both roots and distinct since pp is odd; so these are the only two roots, and a(p−1)/2a^{(p-1)/2} must be one of them. No other residue class, like 22, can satisfy y2≡1(modp)y^2\equiv1\pmod p unless pp happens to divide (2−1)(2+1)=3(2-1)(2+1)=3, i.e. only in the special tiny case p=3p=3 would 2≡−1(mod3)2\equiv-1\pmod3 coincide with the allowed value −1-1 — consistent, not a counterexample.

Is the converse of Euler's Criterion also true — if a(p−1)/2≡1a^{(p-1)/2}\equiv1, is aa necessarily a quadratic residue?

Yes, and this converse is exactly the content proved in Step 5 of the proof above, via the counting argument: since there are exactly (p−1)/2(p-1)/2 quadratic residues and the polynomial x(p−1)/2−1x^{(p-1)/2}-1 has at most (p−1)/2(p-1)/2 roots, the residues account for all the roots, leaving no room for any nonresidue to also satisfy the congruence. So the two directions "residue ⇒a(p−1)/2≡1\Rightarrow a^{(p-1)/2}\equiv1" and "a(p−1)/2≡1⇒a^{(p-1)/2}\equiv1 \Rightarrow residue" are logically intertwined in this proof, both established simultaneously by the counting argument rather than proved as separate implications.

What role does the assumption gcd⁡(a,p)=1\gcd(a,p)=1 play?

It ensures aa is a unit modulo pp, so that a(p−1)/2a^{(p-1)/2} is a well-defined nonzero element to which Fermat's Little Theorem applies. If p∣ap \mid a, then a≡0(modp)a\equiv0\pmod p, and a(p−1)/2≡0(modp)a^{(p-1)/2}\equiv0\pmod p as well, which trivially matches the convention (ap)=0\left(\frac ap\right)=0, but this case sits outside the "residue vs. nonresidue" dichotomy the theorem is built to distinguish and is handled by definition rather than by the proof's counting argument.

Before this

Where this leads