Difference between revisions of "Euler's Totient Theorem"
(headers) |
|||
| Line 1: | Line 1: | ||
| − | + | '''Euler's Totient Theorem''' is a theorem closely related to his [[totient function|function of the same name]]. | |
| + | == Theorem == | ||
Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>, then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>. | Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>, then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>. | ||
| − | + | == Credit == | |
This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies that <math>{m}</math> is prime. For this reason it is known as Euler's generalization and Fermat-Euler as well. | This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies that <math>{m}</math> is prime. For this reason it is known as Euler's generalization and Fermat-Euler as well. | ||
| − | + | == See also == | |
* [[Number theory]] | * [[Number theory]] | ||
Revision as of 17:01, 24 November 2007
Euler's Totient Theorem is a theorem closely related to his function of the same name.
Theorem
Let 
be Euler's totient function. If 
is an integer and 
is a positive integer relatively prime to 
, then 
.
Credit
This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies that 
is prime. For this reason it is known as Euler's generalization and Fermat-Euler as well.
