Editing Euler's criterion (section)

==Proof==

The proof uses the fact that the residue classes modulo a prime number are a [[Field (mathematics)|field]]. See the article [[Characteristic (algebra)#Case of fields|prime field]] for more details.

Because the modulus is prime, [[Lagrange's theorem (number theory)|Lagrange's theorem]] applies: a polynomial of degree {{mvar|k}} can only have at most {{mvar|k}} roots. In particular, {{math|''x''{{sup|2}} &equiv; ''a'' (mod ''p'')}} has at most 2 solutions for each {{mvar|a}}. This immediately implies that besides 0 there are at least {{math|{{sfrac|''p'' − 1|2}}}} distinct quadratic residues modulo {{mvar|p}}: each of the {{math|''p'' − 1}} possible values of {{mvar|x}} can only be accompanied by one other to give the same residue.

In fact, <math> (p-x)^{2}\equiv x^{2} \pmod p.</math>This is because <math> (p-x)^{2} \equiv p^{2}-{2}{x}{p}+x^{2} \equiv x^{2} \pmod p.</math>
So, the <math> \tfrac{p-1}{2}</math> distinct quadratic residues are:
<math>1^{2}, 2^{2}, ... , (\tfrac{p-1}{2})^{2} \pmod p. </math>
 
As {{mvar|a}} is coprime to {{mvar|p}}, [[Fermat's little theorem]] says that
:<math>
a^{p-1}\equiv 1 \pmod p,
</math>
which can be written as
:<math>
\left( a^{\tfrac{p-1}{2}}-1 \right)\left( a^{\tfrac{p-1}{2}}+1 \right)    \equiv 0 \pmod p.
</math>
Since the integers mod {{mvar|p}} form a field, for each {{mvar|a}}, one or the other of these factors must be zero. Therefore,

:<math>
a^{\tfrac{p-1}{2}}\equiv 1\pmod p
</math> or

:<math>
a^{\tfrac{p-1}{2}} \equiv {-1}\pmod p.
</math>

Now if {{mvar|a}} is a quadratic residue, {{math|''a'' ≡ ''x''<sup>2</sup>}},
:<math>
a^{\tfrac{p-1}{2}}\equiv {(x^2)}^{\tfrac{p-1}{2}} \equiv x^{p-1}\equiv1\pmod p.
</math>
So every quadratic residue (mod {{mvar|p}}) makes the first factor zero.

Applying Lagrange's theorem again, we note that there can be no more than {{math|{{sfrac|''p'' − 1|2}}}} values of {{mvar|a}} that make the first factor zero. But as we noted at the beginning, there are at least {{math|{{sfrac|''p'' − 1|2}}}} distinct quadratic residues (mod {{mvar|p}}) (besides 0). Therefore, they are precisely the residue classes that make the first factor zero. The other {{math|{{sfrac|''p'' − 1|2}}}} residue classes, the nonresidues, must make the second factor zero, or they would not satisfy Fermat's little theorem. This is Euler's criterion.

===Alternative proof===

This proof only uses the fact that any congruence <math>kx\equiv l\!\!\! \pmod p</math> has a unique (modulo <math>p</math>) solution <math>x</math> provided <math>p</math> does not divide <math>k</math>. (This is true because as <math>x</math> runs through all nonzero remainders modulo <math>p</math> without repetitions, so does <math>kx</math>: if we have <math>kx_1\equiv kx_2 \pmod p</math>, then <math>p\mid k(x_1-x_2)</math>, hence <math>p\mid (x_1-x_2)</math>, but <math>x_1</math> and <math>x_2</math> aren't congruent modulo <math>p</math>.) It follows from this fact that all nonzero remainders modulo <math>p</math> the square of which isn't congruent to <math>a</math> can be grouped into unordered pairs <math>(x,y)</math> according to the rule that the product of the members of each pair is congruent to <math>a</math> modulo <math>p</math> (since by this fact for every <math>y</math> we can find such an <math>x</math>, uniquely, and vice versa, and they will differ from each other if <math>y^2</math> is not congruent to <math>a</math>). If <math>a</math> is not a quadratic residue, this is simply a regrouping of all <math>p-1</math> nonzero residues into <math>(p-1)/2</math> pairs, hence we conclude that <math>1\cdot2\cdot ... \cdot (p-1)\equiv a^{\frac{p-1}{2}} \!\!\! \pmod p</math>. If <math>a</math> is a quadratic residue, exactly two remainders were not among those paired, <math>r</math> and <math>-r</math> such that <math>r^2\equiv a\!\!\! \pmod p</math>. If we pair those two absent remainders together, their product will be <math>-a</math> rather than <math>a</math>, whence in this case <math>1\cdot2\cdot ... \cdot (p-1)\equiv -a^{\frac{p-1}{2}} \!\!\! \pmod p</math>. In summary, considering these two cases we have demonstrated that for <math>a\not\equiv 0 \!\!\! \pmod p</math> we have <math>1\cdot2\cdot ... \cdot (p-1)\equiv -\left(\frac{a}{p}\right)a^{\frac{p-1}{2}} \!\!\! \pmod p</math>. It remains to substitute <math>a=1</math> (which is obviously a square) into this formula to obtain at once [[Wilson's theorem]], Euler's criterion, and (by squaring both sides of Euler's criterion) [[Fermat's little theorem]].