Euler's Criterion - Proof

Proof

The proof uses fact that the residue classes modulo a prime number are a field. See the article prime field for more details. The fact that there are (p − 1)/2 quadratic residues and the same number of nonresidues (mod p) is proved in the article quadratic residue.

Fermat's little theorem says that

a^{p-1}\equiv 1 \pmod p.

This can be written as

(a^{\tfrac{p-1}{2}}-1)(a^{\tfrac{p-1}{2}}+1)\equiv 0 \pmod p.

Since the integers mod p form a field, one or the other of these factors must be congruent to zero.

Now if a is a quadratic residue, a ≡ x2,

a^{\tfrac{p-1}{2}}\equiv{x^2}^{\tfrac{p-1}{2}}\equiv x^{p-1}\equiv1\pmod p.

So every quadratic residue (mod p) makes the first factor zero.

Lagrange's theorem says that there can be no more than (p − 1)/2 values of a that make the first factor zero. But it is known that there are (p − 1)/2 distinct quadratic residues (mod p). Therefore they are precisely the residue classes that make the first factor zero. The other (p − 1)/2 residue classes, the nonresidues, must be the ones making the second factor zero. This is Euler's criterion.

Read more about this topic:  Euler's Criterion

Famous quotes containing the word proof:

    “Right and proof are two crutches for everything bent and crooked that limps along.”
    —Franz Grillparzer (1791–1872)

    “There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)