Euler's Totient Theorem

Euler's Totient Theorem is a theorem closely related to his totient function.

Theorem

Let $\phi(n)$ be Euler's totient function. If ${a}$ is an integer and $m$ is a positive integer relatively prime to $a$ ,in other words If $n$ is a positive integer, $\phi{(n)}$ is the number of integers in the range $\{1,2,3\cdots{,n}\}$ which are relatively prime to $n$ .Then ${a}^{\phi (m)}\equiv 1 \pmod {m}$ .

Credit

This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies that ${m}$ is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.

Proof

Consider the set of numbers $A =$ { $n_1, n_2, ... n_{\phi(m)}$ } (mod m) such that the elements of the set are the numbers relatively prime to $m$ . It will now be proved that this set is the same as the set $B =$ { $an_1, an_2, ... an_{\phi(m)}$ } (mod m) where $(a, m) = 1$ . All elements of $B$ are relatively prime to $m$ so if all elements of $B$ are distinct, then $B$ has the same elements as $A$ . This means that $n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}$ (mod m) → $a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}$ (mod m) → $a^{\phi (m)} \equiv 1$ (mod m) as desired.

Page

Toolbox

Search

Euler's Totient Theorem

Contents

Theorem

Credit

Proof

See also