# Euler totient function

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
VIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]

## Definitions

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 (cyclic elements) in a 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}\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-phi 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 if coprime

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

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