Euler's Criterion

Number Theory · Axiom Academy

A powerful tool for computing Legendre symbols and determining quadratic residues For any integer a and odd prime p with gcd( a , p ) = 1, Euler's Criterion states: where ( a / p ) is the Legendre symbol, defined as: ( a / p ) = +1 if a is a quadratic residue mod p ( a / p ) = -1 if a is a quadratic non-residue mod p The proof uses Fermat's Little Theorem and properties of quadratic residues. Step 1: Factor the left side as a difference of squares: Step 2: Since p is prime and divides the product, p must divide at least one factor. Therefore: Step 3: Now consider two cases: Let's use Euler's Criterion to determine whether numbers are quadratic residues.

This is the written version of the interactive lesson above. See the full Number Theory course.