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:

    “If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
    —Susan B. Anthony (1820–1906)

    “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)

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)