Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(658 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
{{about|Euler's theorem in number theory|other meanings|List of topics named after Leonhard Euler}}
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.
In [[number theory]], '''Euler's theorem''' (also known as the '''Fermat–Euler theorem''' or '''Euler's totient theorem''') states that if ''n''  and ''a'' are [[coprime]] positive integers, then
:<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>
where φ(''n'') is [[Euler's totient function]]. (The notation is explained in the article [[Modular arithmetic]].) It was first stated and proved by [[Leonhard Euler]] in 1736.<ref>{{mathworld|EulersTotientTheorem|Euler's Totient Theorem}}</ref>


There is a converse of Euler's theorem: if the above congruence is true then ''a'' and ''n'' must be coprime.
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.


The theorem is a generalization of [[Fermat's little theorem]], and is further generalized by [[Carmichael function|Carmichael's theorem]].
Registered users will be able to choose between the following three rendering modes:


The theorem may be used to easily reduce large powers modulo ''n''. For example, consider finding the ones place decimal digit of 7<sup>222</sup>, i.e. 7<sup>222</sup> (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 7<sup>4</sup> ≡ 1 (mod 10), and we get 7<sup>222</sup> ≡ 7<sup>4×55 + 2</sup> ≡ (7<sup>4</sup>)<sup>55</sup>×7<sup>2</sup> ≡ 1<sup>55</sup>×7<sup>2</sup> ≡ 49 ≡ 9 (mod 10).
'''MathML'''
:<math forcemathmode="mathml">E=mc^2</math>


In general, when reducing a power of ''a'' modulo ''n'' (where ''a'' and ''n'' are coprime), one needs to work modulo φ(''n'') in the exponent of ''a'':
<!--'''PNG''' (currently default in production)
:if ''x'' ≡ ''y'' (mod φ(''n'')), then ''a''<sup>''x''</sup> ≡ ''a''<sup>''y''</sup> (mod ''n'').
:<math forcemathmode="png">E=mc^2</math>


Euler's theorem also forms the basis of the [[RSA (algorithm)|RSA]] encryption system: encryption and decryption in this system together amount to exponentiating the original text by ''k''φ(''n'')+1 for some positive integer ''k'', so Euler's theorem shows that the decrypted result is the same as the original.
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


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


1. Euler's theorem can be proven using concepts from the [[group (mathematics)|theory of groups]]:<ref>Ireland & Rosen, corr. 1 to prop 3.3.2</ref>
==Demos==
The residue classes (mod ''n'') that are coprime to ''n'' form a group under multiplication (see the article [[Multiplicative group of integers modulo n]] for details.) [[Lagrange's theorem (group theory)|Lagrange's theorem]] states that the order of any subgroup of a finite group divides the order of the entire group, in this case φ(''n''). If ''a'' is any number coprime to ''n'' then ''a'' is in one of these residue classes, and its powers ''a'', ''a''<sup>2</sup>, ..., ''a''<sup>''k''</sup> &equiv; 1 (mod ''n'') are a subgroup. Lagrange's theorem says ''k'' must divide φ(''n''), i.e. there is an integer ''M'' such that ''kM'' = φ(''n''). But then,
:<math>
a^{\varphi(n)} =  
a^{kM} =  
(a^{k})^M \equiv
1^M =  
1 \pmod{n}.
</math>


2. There is also a direct proof:<ref>Hardy & Wright, thm. 72</ref><ref>Landau, thm. 75</ref> Let ''R'' = {''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>φ(''n'')</sub>} be a [[reduced residue system]] (mod  ''n'') and let ''a'' be any integer coprime to ''n''. The proof hinges on the fundamental fact that multiplication by ''a'' permutes the ''x''<sub>''i''</sub>: in other words if ''ax''<sub>''j''</sub>  &equiv; ''ax''<sub>''k''</sub>  (mod ''n'') then ''j'' = ''k''. (This law of cancellation is proved in the article [[Multiplicative_group_of_integers_modulo_n#Group_axioms|Multiplicative group of integers modulo n]].<ref>See [[Bézout's lemma]]</ref>) That is, the sets ''R'' and ''aR'' = {''ax''<sub>1</sub>, ''ax''<sub>2</sub>, ..., ''ax''<sub>φ(''n'')</sub>}, considered as sets of congruence classes (mod ''n''), are identical (as sets - they may be listed in different orders), so the product of all the numbers in ''R'' is congruent (mod ''n'') to the product of all the numbers in ''aR'':
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:
:<math>
\prod_{i=1}^{\varphi(n)} x_i \equiv
\prod_{i=1}^{\varphi(n)} ax_i \equiv
a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n},
</math> and using the cancellation law to cancel the ''x''<sub>''i''</sub>s gives Euler's theorem:


:<math>
a^{\varphi(n)}\equiv 1 \pmod{n}.
</math>


==See also==
* accessibility:
* [[Carmichael function]]
** 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]]
* [[Euler's criterion]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
* [[Fermat's little theorem]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
* [[Wilson's theorem]]
** [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.


==Notes==
==Test pages ==
{{reflist}}


==References==
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
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.
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


*{{citation
*[[Inputtypes|Inputtypes (private Wikis only)]]
  | last1 = Gauss  | first1 = Carl Friedrich
*[[Url2Image|Url2Image (private Wikis only)]]
  | last2 = Clarke | first2 = Arthur A. (translator into English) 
==Bug reporting==
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
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 .
  | publisher = [[Springer Publishing|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 = Ireland  | first1 = Kenneth
  | last2 = Rosen  | first2 = Michael
  | title = A Classical Introduction to Modern Number Theory (Second edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | date = 1990
  | isbn = 0-387-97329-X}}
*{{citation
  | last1 = Landau | first1 = Edmund
  | title = Elementary Number Theory
  | publisher = Chelsea
  | location = New York
  | date = 1966}}
 
== External links ==
* {{mathworld|EulersTotientTheorem|Euler's Totient Theorem}}
* [http://planetmath.org/encyclopedia/EulersTheorem.html Euler's Theorem] at [http://planetmath.org PlanetMath]
 
[[Category:Modular arithmetic]]
[[Category:Theorems in number theory]]
[[Category:Articles containing proofs]]
{{Link GA|es}}
 
[[ar:مبرهنة أويلر]]
[[bg:Теорема на Ойлер]]
[[ca:Teorema d'Euler]]
[[cs:Eulerova věta (teorie čísel)]]
[[da:Eulers sætning]]
[[de:Satz von Euler]]
[[el:Θεώρημα του Όιλερ]]
[[es:Teorema de Euler]]
[[fa:قضیه اویلر]]
[[fr:Théorème d'Euler (nombres)]]
[[ko:오일러의 정리]]
[[id:Teorema Euler]]
[[is:Eulersregla]]
[[it:Teorema di Eulero (aritmetica modulare)]]
[[he:משפט אוילר]]
[[kk:Эйлер теоремасы (сандар теориясы)]]
[[hu:Euler–Fermat-tétel]]
[[nl:Stelling van Euler]]
[[ja:オイラーの定理 (数論)]]
[[pl:Twierdzenie Eulera (teoria liczb)]]
[[pt:Teorema de Euler]]
[[ro:Teorema lui Euler]]
[[ru:Теорема Эйлера (теория чисел)]]
[[fi:Eulerin lause (lukuteoria)]]
[[sv:Eulers sats]]
[[tr:Euler teoremi]]
[[uk:Теорема Ейлера (теорія чисел)]]
[[vi:Định lý Euler]]
[[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"