Suppose you want to know whether a is a quadratic residue modulo some large prime p — is there some x with x^2 \equiv a \pmod p? The honest, brute-force way is to square every residue 1, 2, \dots, p-1 and see whether a turns up in the list. For p = 23 that's a couple of dozen squarings — mildly tedious. For a 2048-bit prime used in real cryptography, that list has more entries than there are atoms in the observable universe. Brute force is not an option.

Euler found something remarkable: you don't need the whole list at all. A single exponentiation — raise a to the power (p-1)/2 and reduce mod p — always comes out to exactly +1 or exactly -1, and it tells you the answer outright. Combined with fast modular exponentiation (square-and-multiply), that one computation takes only about \log_2 p steps — for a 2048-bit prime, a couple of thousand multiplications instead of an astronomically long search. This is Euler's criterion, and it turns "is a a square mod p?" from an exhaustive search into a fast, direct formula.

The criterion

Test it mod 7 with (p-1)/2 = 3: 2^{3} = 8 \equiv 1 (so 2 is a residue) but 3^{3} = 27 \equiv 6 \equiv -1 (so 3 is a non-residue) — matching what we found by hand from the residue list \{1, 4, 2\} mod 7.

Why it works

By Fermat's Little Theorem, a^{p-1} \equiv 1 \pmod p whenever p \nmid a. Write that as

So a^{(p-1)/2} is a square root of 1 modulo a prime, and the only square roots of 1 mod a prime are \pm 1 (if x^2 \equiv 1 then p \mid (x-1)(x+1), and a prime dividing a product divides one of the factors). That already proves the value is always +1 or -1 — the hard part is matching the sign to "residue" or "non-residue".

If a = x^2 is a residue, substitute directly: a^{(p-1)/2} = x^{p-1} \equiv 1 by Fermat again. That accounts for the residues. The order of a primitive root g is exactly p-1, and every nonzero residue is some power g^k; a short count shows g^k is a square exactly when k is even, so there are precisely (p-1)/2 quadratic residues and (p-1)/2 non-residues among 1, \dots, p-1. Since the polynomial t^{(p-1)/2} - 1 has at most (p-1)/2 roots mod p, and we've already found that many (the residues), the non-residues must be the leftover roots of t^{(p-1)/2} + 1 \equiv 0 — giving -1 exactly as claimed. (This is also exactly what Euler's more general theorem about orders and powers predicts once you replace the prime modulus by Euler's totient exponent — for a prime p that exponent is simply p-1.)

A small case makes the counting argument concrete. Take p = 5, so (p-1)/2 = 2. The nonzero residues are 1, 2, 3, 4, and a primitive root is g = 2, since its powers 2^1, 2^2, 2^3, 2^4 \equiv 2, 4, 3, 1 cycle through all four of them before repeating. Writing each residue as a power of g, the ones with an even exponent — 2^2 \equiv 4 and 2^4 \equiv 1 — are exactly the two quadratic residues mod 5, while the odd-exponent powers 2^1 \equiv 2 and 2^3 \equiv 3 are the two non-residues. Raise each to the 2nd power (i.e. to the (p-1)/2 power) and the residues' exponents double to a multiple of 4 = p - 1, collapsing to 1; the non-residues' exponents double to an odd multiple of 2, landing on g^2 \equiv 4 \equiv -1. That even/odd split of the exponent is the entire mechanism behind the +1/-1 split in the general theorem.

Worked example: a formula test that agrees with the list

Take p = 13, so (p-1)/2 = 6. First, the slow way — square every residue from 1 to 12 mod 13:

The distinct values that appear are \{1, 3, 4, 9, 10, 12\} — the six quadratic residues mod 13. Is a = 7 on that list? No — so 7 should be a non-residue.

Now the fast way: compute 7^{6} \bmod 13 by repeated squaring, reducing at every step so the numbers never grow large.

7^{6} \equiv -1 — Euler's criterion says non-residue, exactly matching the list. Try it the other way with a = 4, which is on the residue list: 4^2 = 16 \equiv 3, 4^4 \equiv 3^2 = 9, 4^6 \equiv 4^4 \cdot 4^2 \equiv 9 \cdot 3 = 27 \equiv 1 \pmod{13} — a clean +1, as it must be. Notice the criterion only needed three squarings and one extra multiplication either time — no list of twelve squares required.

Scale that up and the saving becomes dramatic rather than merely convenient. For p = 97, the brute-force list has forty-eight squarings to compute and compare against. The criterion instead needs (p-1)/2 = 48 as an exponent, but square-and-multiply reaches it in only about \log_2 48 \approx 6 squarings plus a handful of multiplications along the way — roughly eight modular multiplications total, however large a is. Double the size of the prime again and the brute-force list doubles in length, while the fast exponentiation only costs one extra squaring. That gap between "grows with p" and "grows with \log_2 p" is exactly why real cryptographic software can afford to test residues against primes with hundreds of digits, thousands of times a second.

What it unlocks

Euler's criterion makes the Legendre symbol an honest computation and immediately proves the \left(\tfrac{-1}{p}\right) rule (put a = -1 and read off the sign from the parity of (p-1)/2). Pushed harder with a more delicate counting argument, it yields the supplementary law for \left(\tfrac{2}{p}\right), and it underpins the crown jewel, quadratic reciprocity, which pushes the computability even further by relating \left(\tfrac{p}{q}\right) to \left(\tfrac{q}{p}\right) for two different primes.

There is also a second, quieter payoff. Because the criterion is genuinely an equality of numbers modulo p — not just a yes/no test — it slots directly into larger algebraic arguments as an ordinary congruence you can multiply, substitute, and combine with other facts about powers. That is precisely the property that later lets reciprocity be proved by counting how certain related quantities behave mod p, rather than by brute enumeration. Euler's one-line formula is small, but it is the load-bearing wall the rest of quadratic residue theory is built on.