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:

    “a meek humble Man of modest sense,
    Who preaching peace does practice continence;
    Whose pious life’s a proof he does believe,
    Mysterious truths, which no Man can conceive.”
    —John Wilmot, 2d Earl Of Rochester (1647–1680)

    “A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
    —Samuel Johnson (1709–1784)

    “It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
    —William Shakespeare (1564–1616)