# Euler totient function

VIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]

## Definitions

The Euler totient function, also known as the Euler-phi function, on a natural number $n$, denoted $\varphi(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 the Euler totient function on positive divisors

For any natural number $n$, we have $n=\sum_{d|n}\varphi(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 $\varphi(p^{k})=p^{k-1}(p-1)$. This is an immediate application of the previous fact.

### Multiplicative function

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

## Explicit formula

Knowing the prime factorization of $n$, we can evaluate $\varphi(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 $\varphi(n)=n\prod_{p}(1-\frac1{p})$, where here the product is evaluated over all distinct prime factors of $n$.