Editing Euler's theorem

{{short description|Theorem on modular exponentiation}}
{{about|Euler's theorem in number theory||List of things named after Leonhard Euler#Theorems}}
In [[number theory]], '''Euler's theorem''' (also known as the '''Fermat–Euler theorem''' or '''Euler's totient theorem''') states that, if {{math|''n''}} and {{math|''a''}} are [[coprime]] positive integers, then <math>a^{\varphi(n)}</math> is congruent to <math>1</math>  [[modular arithmetic|modulo]] {{math|''n''}}, where <math>\varphi</math>  denotes [[Euler's totient function]]; that is
:<math>a^{\varphi (n)} \equiv 1 \pmod{n}.</math>

In 1736, [[Leonhard Euler]] published a proof of [[Fermat's little theorem]]<ref>See:
*  Leonhard Euler (presented:  August 2, 1736; published: 1741) [https://books.google.com/books?id=-ssVAAAAYAAJ&pg=RA1-PA141 "Theorematum quorundam ad numeros primos spectantium demonstratio"] (A proof of certain theorems regarding prime numbers), ''Commentarii academiae scientiarum Petropolitanae'', '''8''' : 141–146.
*  For further details on this paper, including an English translation, see:  [https://scholarlycommons.pacific.edu/euler-works/54/ The Euler Archive].</ref> (stated by [[Pierre de Fermat|Fermat]] without proof), which is the restriction of Euler's theorem to the case where {{mvar|n}} is a prime number.  Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where {{mvar|n}} is not prime.<ref>See:
*  L. Euler (published: 1763) [https://books.google.com/books?id=5uEAAAAAYAAJ&pg=PA74 "Theoremata arithmetica nova methodo demonstrata"] (Proof of a new method in the theory of arithmetic), ''Novi Commentarii academiae scientiarum Petropolitanae'', '''8''' : 74–104.  Euler's theorem appears as "Theorema 11" on page 102.  This paper was first presented to the Berlin Academy on June 8, 1758 and to the St. Petersburg Academy on October 15, 1759.  In this paper, Euler's totient function, <math>\varphi(n)</math>, is not named but referred to as "numerus partium ad ''N'' primarum" (the number of parts prime to ''N''; that is, the number of natural numbers that are smaller than ''N'' and relatively prime to ''N'').
*  For further details on this paper, see: [http://www.math.dartmouth.edu/~euler/pages/E271.html The Euler Archive].
*  For a review of Euler's work over the years leading to Euler's theorem, see: [http://people.wcsu.edu/sandifere/History/Preprints/Talks/Rowan%202005%20Euler's%20three%20proofs.pdf Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"] {{Webarchive|url=https://web.archive.org/web/20060828195053/http://people.wcsu.edu/sandifere/History/Preprints/Talks/Rowan%202005%20Euler%27s%20three%20proofs.pdf |date=2006-08-28 }}</ref>

The converse of Euler's theorem is also true: if the above congruence is true, then <math>a</math> and <math>n</math> must be coprime.

The theorem  is further generalized by some of [[Carmichael function#Carmichael's theorems|Carmichael's theorems]].

The theorem may be used to easily reduce large powers modulo <math>n</math>. For example, consider finding the ones place decimal digit of <math>7^{222}</math>, i.e. <math>7^{222} \pmod{10}</math>. The integers 7 and 10 are coprime, and <math>\varphi(10) = 4</math>. So Euler's theorem yields <math>7^4 \equiv 1 \pmod{10}</math>, and we get <math>7^{222} \equiv 7^{4 \times 55 + 2} \equiv (7^4)^{55} \times 7^2 \equiv 1^{55} \times 7^2 \equiv 49 \equiv 9 \pmod{10}</math>.

In general, when reducing a power of <math>a</math> modulo <math>n</math> (where <math>a</math> and <math>n</math> are coprime), one needs to work modulo <math>\varphi(n)</math> in the exponent of <math>a</math>:
:if <math>x \equiv y \pmod{\varphi(n)}</math>, then <math>a^x \equiv a^y \pmod{n}</math>.

Euler's theorem underlies the [[RSA (cryptosystem)|RSA cryptosystem]], which is widely used in [[Internet]] communications. In this cryptosystem, Euler's theorem is used with {{mvar|n}} being a product of two large [[prime number]]s, and the security of the system is based on the difficulty of [[integer factorization|factoring]] such an integer.

== Proofs ==
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> 
The residue classes modulo {{mvar|n}} that are coprime to {{mvar|n}} form a group under multiplication (see the article [[Multiplicative group of integers modulo n|Multiplicative group of integers modulo ''n'']] for details). The [[Order (group theory)|order]] of that group is {{math|''φ''(''n'')}}. [[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 {{math|''φ''(''n'')}}. If {{mvar|a}} is any number [[coprime]] to {{mvar|n}} then {{mvar|a}} is in one of these residue classes, and its powers {{math|''a'', ''a''{{sup|2}}, ... , ''a''{{sup|''k''}}}} modulo {{mvar|n}} form a subgroup of the group of residue classes, with {{math|''a''{{sup|''k''}} &equiv; 1 (mod ''n'')}}. Lagrange's theorem says {{mvar|k}} must divide {{math|''φ''(''n'')}}, i.e. there is an integer {{mvar|M}} such that {{math|''kM'' {{=}} ''φ''(''n'')}}. This then implies,
:<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 {{math|''R'' {{=}} {{(}}''x''{{sub|1}}, ''x''{{sub|2}}, ... , ''x''{{sub|''φ''(''n'')}}{{)}}}} be a [[reduced residue system]] ({{math|mod ''n''}}) and let {{mvar|a}} be any integer coprime to {{mvar|n}}. The proof hinges on the fundamental fact that multiplication by {{mvar|a}} permutes the {{mvar|x{{sub|i}}}}: in other words if {{math|''ax{{sub|j}}'' &equiv; ''ax{{sub|k}}'' (mod ''n'')}} then {{math|''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 {{mvar|R}} and {{math|''aR'' {{=}} {{(}}''ax''{{sub|1}}, ''ax''{{sub|2}}, ... , ''ax''{{sub|''φ''(''n'')}}{{)}}}}, considered as sets of congruence classes ({{math|mod ''n''}}), are identical (as sets—they may be listed in different orders), so the product of all the numbers in {{mvar|R}} is congruent ({{math|mod ''n''}}) to the product of all the numbers in {{mvar|aR}}:
:<math>
\prod_{i=1}^{\varphi(n)} x_i \equiv 
\prod_{i=1}^{\varphi(n)} ax_i =
a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n},
</math> and using the cancellation law to cancel each {{mvar|x{{sub|i}}}} gives Euler's theorem:

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

==See also==
* [[Carmichael number]]
* [[Euler's criterion]]
* [[Wilson's theorem]]

==Notes==
{{reflist|2}}

==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. (translated into English)  
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = [[Springer Publishing|Springer]]
  | location = New York
  | date = 1986
  | isbn = 0-387-96254-9}}
*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Maser | first2 = H. (translated 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
 |url-access = registration
 |url        = https://archive.org/details/introductiontoth00hard
}}
*{{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/eulerfermattheorem Euler-Fermat Theorem] at [http://planetmath.org PlanetMath]

{{Leonhard Euler}}
{{Portal bar|Mathematics}}

[[Category:Modular arithmetic]]
[[Category:Theorems in number theory]]
[[Category:Articles containing proofs]]
[[Category:Leonhard Euler]]