← Graph View All Domains

A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.

Euler's Criterion

Graduate Depth 90 in the knowledge graph ☐ I know this ☆ Set as goal

2topics build on this

401prerequisites beneath it

See this on the map →

Fermat's Little Theorem Quadratic Residues and the Legendre Symbol→→Law of Quadratic Reciprocity

Core Idea

(a/p) ≡ a^((p-1)/2) (mod p). This criterion computes the Legendre symbol via modular exponentiation and reveals that quadratic residuosity is determined by the group structure of (Z/pZ)*.

Explainer

You already know two things that Euler's Criterion connects: the Legendre symbol (a/p), which tells you whether a is a quadratic residue mod p, and Fermat's Little Theorem, which tells you a^p-1 ≡ 1 (mod p) for any a not divisible by p. Euler's Criterion is what happens when you ask: can Fermat's Little Theorem tell us about squares?

The key algebraic step is to factor. Since a^p-1 ≡ 1 (mod p), we have a^p-1 - 1 ≡ 0 (mod p), which factors as (a^((p-1)/2) - 1)(a^((p-1)/2) + 1) ≡ 0 (mod p). Because p is prime, one of the factors must be zero mod p — so a^((p-1)/2) is either 1 or -1 (mod p). Euler's Criterion asserts exactly which outcome corresponds to which: a is a quadratic residue mod p if and only if a^((p-1)/2) ≡ 1 (mod p), and a non-residue if and only if a^((p-1)/2) ≡ -1 (mod p).

Why does this work? Consider the multiplicative group (ℤ/pℤ)*, which is cyclic of order p-1. Every element can be written as g^k for a fixed generator g. The element g^k is a perfect square in this group if and only if k is even, because g^k = (g^k/2)² only makes sense when k/2 is an integer. Now compute (g^k)^((p-1)/2) = g^(k(p-1)/2). If k is even, this equals (g^p-1)^k/2 = 1^k/2 = 1 by Fermat. If k is odd, the exponent k(p-1)/2 is not a multiple of p-1, and the result is g^((p-1)/2) — the unique element of order 2 in the group, which equals -1 (mod p). The exponent test perfectly separates squares from non-squares.

In practice, Euler's Criterion turns a question about square roots into a fast modular exponentiation. To decide whether 7 is a quadratic residue mod 11, compute 7⁵ mod 11: 7² = 49 ≡ 5, 7⁴ ≡ 25 ≡ 3, 7⁵ ≡ 21 ≡ 10 ≡ -1 (mod 11). So (7/11) = -1, meaning 7 has no square root mod 11 — far more efficient than checking all residue classes individually. This computational power, rooted in the group structure of (ℤ/pℤ)*, is what makes the criterion foundational for the deeper theory of quadratic reciprocity.

Practice Questions 5 questions

Prerequisite Chain

Understanding Zero → The Number Zero → Counting to Five → Counting to 10 → Counting to 20 → Counting a Set of Objects Up to 20 → Cardinality: The Last Number Counted → Matching Numerals to Quantities → Subitizing Small Quantities → Addition Within 10 → Number Bonds to 10 → Addition Within 20 → Doubles and Near Doubles → Doubles Facts Within 10 → Near Doubles Facts Within 20 → Mental Math Strategies for Addition → Mental Math: Adding and Subtracting Tens → Addition Within 100 → Repeated Addition as Multiplication → Multiplication as Equal Groups → Multiplication: Arrays → Basic Multiplication Facts (0s, 1s, 2s, 5s, 10s) → Multiplication Facts Within 100 → Division as Equal Sharing → Division as Grouping (Measurement Division) → Division: Grouping (Repeated Subtraction) Model → Division: Fair Sharing Model → Division as Equal Sharing → Division as Grouping → Basic Division Facts → Division Facts Within 100 → Multiplication and Division Fact Families → Relationship Between Multiplication and Division → Division Facts as Inverse of Multiplication → Remainders and Quotients in Division → Division Word Problems → Multi-Step Word Problems → Solving Multi-Step Word Problems → Multiplication Word Problems → Division Word Problems → Introduction to Long Division → Factors and Multiples → Prime and Composite Numbers → Equivalent Fractions → Relating Fractions and Decimals → Decimal Place Value → Integers and the Number Line → Comparing and Ordering Integers → Absolute Value → Adding Integers → Subtracting Integers → Multiplying Integers → Introduction to Exponents → Order of Operations → Integer Order of Operations → Variable Expressions → The Distributive Property → Variables and Expressions Review → Introduction to Polynomials → Adding and Subtracting Polynomials → Multiplying Polynomials → Factorial → Permutations → Combinations → Counting Principles: Addition and Multiplication Rules → Introduction to Graph Theory → Propositional Logic Foundations → Logical Equivalences → Set Operations: Union, Intersection, and Complement → Proof by Cases → Proving by Cases and Exhaustion → Vacuous Truth and Trivial Cases → Proof by Cases (Proof by Exhaustion) → Mathematical Induction → Divisibility and Greatest Common Divisor → The Fundamental Theorem of Arithmetic → Divisibility Theory (Formal Treatment) → Fundamental Theorem of Arithmetic (Rigorous Proof) → Arithmetic Functions and Multiplicativity → Dirichlet Series and L-Functions → Primes in Arithmetic Progressions (Dirichlet's Theorem) → Distribution of Primes → Introduction to the Riemann Zeta Function → Dirichlet Series and L-Functions → Primes in Arithmetic Progressions (Dirichlet's Theorem) → Wilson's Theorem → Fermat's Little Theorem → Euler's Criterion for Quadratic Residues → Law of Quadratic Reciprocity → Quadratic Residues and the Legendre Symbol → Euler's Criterion

Longest path: 91 steps · 401 total prerequisite topics

Prerequisites (2)

Quadratic Residues and the Legendre Symbolhard Fermat's Little Theoremhard

Leads To (1)

Law of Quadratic Reciprocityhard