# 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.