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:

    “Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
    —Henry David Thoreau (1817–1862)

    “War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.”
    —M.F.K. Fisher (1908–1992)

    “The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
    —Charles Baudelaire (1821–1867)