Open main menu

Groupprops β

Euler totient function


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.


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.