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-phi function on a natural number $n$ , denoted $φ (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} φ (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 $φ (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 $φ (m n) = φ (m) φ (n)$ . For full proof, see Euler-phi function is multiplicative if coprime.

Explicit formula

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