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 18: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.