Euler's criterion
Template:Short description In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let p be an odd prime and a be an integer coprime to p. Then<ref>Gauss, DA, Art. 106</ref><ref>Template:Cite book</ref><ref>Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952</ref>
- <math>
a^{\tfrac{p-1}{2}} \equiv \begin{cases} \;\;\,1\pmod{p}& \text{ if there is an integer }x \text{ such that }x^2\equiv a \pmod{p},\\
-1\pmod{p}& \text{ if there is no such integer.}
\end{cases} </math>
Euler's criterion can be concisely reformulated using the Legendre symbol:<ref>Hardy & Wright, thm. 83</ref>
- <math>
\left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p. </math>
The criterion dates from a 1748 paper by Leonhard Euler.<ref>Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive</ref><ref>L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487</ref>
Proof
[edit]The proof uses the fact that the residue classes modulo a prime number are a field. See the article prime field for more details.
Because the modulus is prime, Lagrange's theorem applies: a polynomial of degree Template:Mvar can only have at most Template:Mvar roots. In particular, Template:Math has at most 2 solutions for each Template:Mvar. This immediately implies that besides 0 there are at least Template:Math distinct quadratic residues modulo Template:Mvar: each of the Template:Math possible values of Template:Mvar 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 Template:Mvar is coprime to Template:Mvar, 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 Template:Mvar form a field, for each Template:Mvar, 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 Template:Mvar is a quadratic residue, Template:Math,
- <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 Template:Mvar) makes the first factor zero.
Applying Lagrange's theorem again, we note that there can be no more than Template:Math values of Template:Mvar that make the first factor zero. But as we noted at the beginning, there are at least Template:Math distinct quadratic residues (mod Template:Mvar) (besides 0). Therefore, they are precisely the residue classes that make the first factor zero. The other Template:Math 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
[edit]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.
Examples
[edit]Example 1: Finding primes for which a is a residue
Let a = 17. For which primes p is 17 a quadratic residue?
We can test prime p's manually given the formula above.
In one case, testing p = 3, we have 17(3 − 1)/2 = 171 ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.
In another case, testing p = 13, we have 17(13 − 1)/2 = 176 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 4.
We can do these calculations faster by using various modular arithmetic and Legendre symbol properties.
If we keep calculating the values, we find:
- (17/p) = +1 for p = {13, 19, ...} (17 is a quadratic residue modulo these values)
- (17/p) = −1 for p = {3, 5, 7, 11, 23, ...} (17 is not a quadratic residue modulo these values).
Example 2: Finding residues given a prime modulus p
Which numbers are squares modulo 17 (quadratic residues modulo 17)?
We can manually calculate it as:
- 12 = 1
- 22 = 4
- 32 = 9
- 42 = 16
- 52 = 25 ≡ 8 (mod 17)
- 62 = 36 ≡ 2 (mod 17)
- 72 = 49 ≡ 15 (mod 17)
- 82 = 64 ≡ 13 (mod 17).
So the set of the quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}. Note that we did not need to calculate squares for the values 9 through 16, as they are all negatives of the previously squared values (e.g. 9 ≡ −8 (mod 17), so 92 ≡ (−8)2 = 64 ≡ 13 (mod 17)).
We can find quadratic residues or verify them using the above formula. To test if 2 is a quadratic residue modulo 17, we calculate 2(17 − 1)/2 = 28 ≡ 1 (mod 17), so it is a quadratic residue. To test if 3 is a quadratic residue modulo 17, we calculate 3(17 − 1)/2 = 38 ≡ 16 ≡ −1 (mod 17), so it is not a quadratic residue.
Euler's criterion is related to the law of quadratic reciprocity.
Applications
[edit]In practice, it is more efficient to use an extended variant of Euclid's algorithm to calculate the Jacobi symbol <math>\left(\frac{a}{n}\right)</math>. If <math>n</math> is an odd prime, this is equal to the Legendre symbol, and decides whether <math>a</math> is a quadratic residue modulo <math>n</math>.
On the other hand, since the equivalence of <math>a^\frac{n-1}{2}</math> to the Jacobi symbol holds for all odd primes, but not necessarily for composite numbers, calculating both and comparing them can be used as a primality test, specifically the Solovay–Strassen primality test. Composite numbers for which the congruence holds for a given <math>a</math> are called Euler–Jacobi pseudoprimes to base <math>a</math>.
Notes
[edit]References
[edit]The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.