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:

    “O, popular applause! what heart of man
    Is proof against thy sweet, seducing charms?”
    —William Cowper (1731–1800)

    “The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
    —Lenny Bruce (1925–1966)

    “The proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
    —Walt Whitman (1819–1892)