Editing Euler's criterion

{{Short description|Formula concerning prime numbers}}
In [[number theory]], '''Euler's criterion''' is a formula for determining whether an [[integer]] is a [[quadratic residue]] [[modular arithmetic|modulo]] a [[prime number|prime]]. Precisely,

Let ''p'' be an [[odd number|odd]] prime and ''a'' be an integer [[coprime]] to ''p''. Then<ref>[[Gauss]], DA, Art. 106</ref><ref>{{cite book|first1 = Joseph B. | last1 = Dense | first2 = Thomas P. | last2 = Dence | title = Elements of the Theory of Numbers | chapter = Theorem 6.4, Chap 6. Residues | page = 197 | publisher = Harcourt Academic Press | year = 1999 | isbn = 9780122091308 | chapter-url = https://books.google.com/books?id=YiYHw7evhjkC&q=euler%27s+criterion+is+it+a+conditional+statement+or+a+biconditional+statement&pg=PA508}}</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==

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]].

==Examples==
'''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<sup>(3 − 1)/2</sup> = 17<sup>1</sup> ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.

In another case, testing ''p'' = 13, we have 17<sup>(13 − 1)/2</sup> = 17<sup>6</sup> ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13.  As confirmation, note that 17 ≡ 4 (mod 13), and 2<sup>2</sup> = 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:
: 1<sup>2</sup> = 1
: 2<sup>2</sup> = 4
: 3<sup>2</sup> = 9
: 4<sup>2</sup> = 16
: 5<sup>2</sup> = 25 ≡ 8 (mod 17)
: 6<sup>2</sup> = 36 ≡ 2 (mod 17)
: 7<sup>2</sup> = 49 ≡ 15 (mod 17)
: 8<sup>2</sup> = 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 9<sup>2</sup> ≡ (−8)<sup>2</sup> = 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<sup>(17 − 1)/2</sup> = 2<sup>8</sup> ≡ 1 (mod 17), so it is a quadratic residue.  To test if 3 is a quadratic residue modulo 17, we calculate 3<sup>(17 − 1)/2</sup> = 3<sup>8</sup> ≡ 16 ≡ −1 (mod 17), so it is not a quadratic residue.

Euler's criterion is related to the [[Quadratic reciprocity|law of quadratic reciprocity]].

==Applications==

In practice, it is more efficient to use an extended variant of [[Euclid's algorithm]] to calculate the [[Jacobi symbol#Calculating the Jacobi symbol|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 pseudoprime]]s to base <math>a</math>.

==Notes==

{{reflist}}

==References==

The ''[[Disquisitiones Arithmeticae]]'' has been translated from Gauss's [[Classical Latin|Ciceronian Latin]] into [[English language|English]] and [[German language|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.

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | translator = Clarke, Arthur A. (English)  
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 1986
  | isbn = 0-387-96254-9}}

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | translator = Maser, H. (German)  
  | title = Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
  | publisher = Chelsea
  | location = New York
  | year = 1965
  | isbn = 0-8284-0191-8}}

*{{citation |last1      = Hardy
 |first1     = G. H.
 |last2      = Wright
 |first2     = E. M.
|author1link = G. H. Hardy
|author2link = E. M. Wright
 |title      = An Introduction to the Theory of Numbers (Fifth edition)
 |publisher  = [[Oxford University Press]]
 |location   = Oxford
 |year       = 1980
 |isbn       = 978-0-19-853171-5
 |url-access = registration
 |url        = https://archive.org/details/introductiontoth00hard
}}

*{{citation
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2000
  | isbn = 3-540-66957-4}}

==External links==
*[http://www.math.dartmouth.edu/~euler/index.html The Euler Archive]

{{DEFAULTSORT:Euler's Criterion}}
[[Category:Articles containing proofs]]
[[Category:Modular arithmetic]]
[[Category:Quadratic residue]]
[[Category:Squares in number theory]]
[[Category:Theorems about prime numbers]]