Euler's criterion

Euler's criterion states that for an odd prime p and an integer a not divisible by p, a^((p−1)/2) is congruent modulo p to the Legendre symbol of a.

Legendre symbol: The Legendre symbol records whether an integer is a quadratic residue modulo an odd prime, with values 0, 1, or −1. The theorem identifies its value with a^((p−1)/2) modulo p.
Congruence relation: Congruence modulo n means two integers have the same remainder upon division by n. The theorem compares a power and a Legendre-symbol value as residue classes.
Quadratic reciprocity: Quadratic reciprocity relates whether one prime is a square modulo another to the reverse residue question. Euler's criterion converts the residue questions in reciprocity into exponent congruences.
Leonhard Euler: Leonhard Euler was an eighteenth-century Swiss mathematician who made foundational contributions across mathematics and physics. The criterion bears Euler's name and belongs to the number theory he developed.
Quadratic residue: A quadratic residue modulo n is a congruence class represented by a square modulo n. Euler's criterion gives a test for quadratic residues when the modulus is prime.
Prime number: A prime number is an integer greater than one with no positive divisors other than one and itself. Primality makes the nonzero residue classes a field and enables the criterion.
Solovay–Strassen primality test: The Solovay–Strassen test uses Euler's criterion to identify many composite numbers probabilistically. Its Euler criterion check compares modular exponentiation with a Jacobi-symbol value.
Adrien-Marie Legendre: Adrien-Marie Legendre was a French mathematician whose work included number theory, analysis, and geometry. His notation for quadratic residues is the symbol appearing in the theorem.
Fermat's little theorem: For prime p and p∤a, Fermat's little theorem states that a^(p−1) is congruent to 1 modulo p. Squaring the criterion's power yields the identity at the heart of Fermat's theorem.
Finite field: A finite field is a field containing finitely many elements, such as the integers modulo a prime. The theorem's arithmetic takes place in the field of residues modulo p.

Linked from 9 pages