Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(647 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
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,
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


Let ''p'' be an [[odd number|odd]] prime and ''a''  an integer [[coprime]] to ''p''. Then<ref>Gauss, DA, Art. 106</ref>
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


:<math>
Registered users will be able to choose between the following three rendering modes:  
a^{\tfrac{p-1}{2}} \equiv
\begin{cases}
\;\;\,1\pmod{p}& \text{ if there is an integer }x \text{ such that }a\equiv x^2 \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>
'''MathML'''
:<math>
:<math forcemathmode="mathml">E=mc^2</math>
\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.
</math>


The criterion first appeared in a 1748 paper by [[Leonhard Euler|Euler]].<ref>Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive</ref>
<!--'''PNG'''  (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


==Proof==
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


The proof uses fact that the residue classes modulo a prime number are a [[finite field|field]]. See the article [[Characteristic_(algebra)#Case_of_fields|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]].
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


[[Fermat's little theorem]] says that
==Demos==
:<math>
a^{p-1}\equiv 1 \pmod p.
</math>
This can be written as
:<math>
(a^{\tfrac{p-1}{2}}-1)(a^{\tfrac{p-1}{2}}+1)\equiv 0 \pmod p.
</math>
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'' &equiv; ''x''<sup>2</sup>,
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:
:<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 ''p'') makes the first factor zero.


[[Lagrange's theorem (number theory)|Lagrange's theorem]] says that there can be no more than (''p''&nbsp;−&nbsp;1)/2 values of ''a'' that make the first factor zero. But it is known that there are (''p''&nbsp;−&nbsp;1)/2 distinct quadratic residues (mod ''p''). Therefore they are precisely the residue classes that make the first factor zero. The other (''p''&nbsp;−&nbsp;1)/2 residue classes, the nonresidues, must be the ones making the second factor zero. This is Euler's criterion.


==Examples==
* accessibility:
'''Example 1: Finding primes for which ''a'' is a residue'''
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


Let ''a'' = 17. For which primes ''p'' is 17 a quadratic residue?
==Test pages ==


We can test prime ''p'''s manually given the formula above.
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


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.
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
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.
==Bug reporting==
 
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
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:
: 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]] and is used in a definition of [[Euler–Jacobi pseudoprime]]s.
 
==See also==
 
==Notes==
 
{{reflist}}
 
==References==
 
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.
 
 
*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Clarke | first2 = Arthur A. (translator into English) 
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | date = 1986
  | isbn = 0-387-96254-9}}
 
*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Maser | first2 = H. (translator into German) 
  | title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
  | publisher = Chelsea
  | location = New York
  | date = 1965
  | isbn = 0-8284-0191-8}}
 
 
*{{citation
  | last1 = Hardy  | first1 = G. H.
  | last2 = Wright | first2 = E. M.
  | title = An Introduction to the Theory of Numbers (Fifth edition)
  | publisher = [[Oxford University Press]]
  | location = Oxford
  | date = 1980
  | isbn = 978-0-19-853171-5}}
 
*{{citation
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | date = 2000
  | isbn = 3-540-66957-4}}
 
==External links==
 
*[http://www.math.dartmouth.edu/~euler/index.html The Euler Archive]
 
{{DEFAULTSORT:Euler's Criterion}}
[[Category:Modular arithmetic]]
[[Category:Articles containing proofs]]
[[Category:Quadratic residue]]
[[Category:Theorems about prime numbers]]
 
[[ca:Criteri d'Euler]]
[[es:Criterio de Euler]]
[[fr:Critère d'Euler]]
[[it:Criterio di Eulero]]
[[he:מבחן אוילר]]
[[pl:Kryterium Eulera]]
[[sv:Eulers kriterium]]
[[zh:欧拉准则]]

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"