proof of Euler’s criterion

(All congruencesMathworldPlanetmathPlanetmathPlanetmath are modulo p for the proof; omitted for clarity.)



Then x21 by Fermat’s Little TheoremMathworldPlanetmath. Thus:


Now consider the two possibilities:

  • If a is a quadratic residueMathworldPlanetmath then by definition, ab2 for some b. Hence:

  • It remains to show that a(p-1)/2-1 if a is a quadratic non-residue. We can proceed in two ways:

    Proof (a)

    PartitionMathworldPlanetmathPlanetmath the set { 1,,p-1} into pairs {c,d} such thatcda. Then c and d must always be distinct since a is a non-residue. Hence, the productPlanetmathPlanetmath of the union of the partitions is:


    and the result follows by Wilson’s Theorem.

    Proof (b)

    The equation:


    has at most (p-1)/2 roots. But we already know of (p-1)/2 distinct roots of the above equation, these being the quadratic residues modulo p. So a can’t be a root, yet a(p-1)/2±1. Thus we must have:



Title proof of Euler’s criterion
Canonical name ProofOfEulersCriterion
Date of creation 2013-03-22 12:41:53
Last modified on 2013-03-22 12:41:53
Owner Koro (127)
Last modified by Koro (127)
Numerical id 7
Author Koro (127)
Entry type Proof
Classification msc 11A15