Euler totient function

This article is about a basic definition in group theory. The article text may, however, contain advanced material.
VIEW: Definitions built on this | Facts about this: (facts closely related to Euler totient function, all facts related to Euler totient function) |Survey articles about this | Survey articles about definitions built on this
VIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]

View a complete list of basic definitions in group theory | Go through a guided tour for beginners to this wiki

Definitions

The Euler totient function, also known as the Euler-phi function, on a natural number $n$, denoted $\phi (n)$, is defined in the following equivalent ways:

1. as the number of positive integers not greater than $n$ that are coprime to $n$.
2. as the number of generators of the cyclic group of order $n$.

Facts

Every natural number is the sum of Euler-phi function on positive divisors

For any natural number $n$, we have $n={\sum }_{d|n}\phi (n)$, where the summation runs over all positive divisors of $n$.

Evaluation on prime powers

For any prime $p$ and positive integer $k$, the value of Euler totient function on $p^k$ is given by the formula $\phi (p^k)=p^{k-1}(p-1)$. This is an immediate application of the previous fact.

Multiplicative if coprime

The Euler-phi function is multiplicative on coprime numbers, that is, if $m$ and $n$ are coprime, then $\phi (mn)=\phi (m)\phi (n)$. For full proof, see Euler-phi function is multiplicative if coprime.

Explicit formula

Knowing the prime factorization of $n$, we can evaluate $\phi (n)$ by repeated applications of the above facts.
However, knowing only the distinct prime factors of the number is sufficient, because the value of Euler totient function on it is then given by the formula $\phi (n)=n{\prod }_p(1-\frac{1}{p})$, where here the product is evaluated over all distinct prime factors of $n$.