Euler totient function

This article defines an arithmetic function or number-theoretic function: a function from the natural numbers to a ring (usually, the ring of integers, rational numbers, real numbers, or complex numbers).
View a complete list of arithmetic functions

Definition

Let $n$ be a natural number. The Euler phi-function or Euler totient function of $n$ , denoted $φ (n)$ , is defined as following:

It is the order of the multiplicative group modulo $n$ , i.e., the multiplicative group of the ring of integers modulo $n$ .
It is the number of elements in ${1, 2, \dots, n}$ that are relatively prime to $n$ .

In terms of prime factorization

Suppose we have the following prime factorization of $n$ :

$n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ .

Then, we have:

$φ (n) = \prod_{i = 1}^{r} p_{i}^{k_{i}} (1 - \frac{1}{p_{i}})$ .

In other words:

$\frac{φ (n)}{n} = \prod_{i = 1}^{r} (1 - \frac{1}{p_{i}})$ .

Properties

Property	Satisfied?	Statement with symbols
multiplicative function	Yes	If $m$ and $n$ are relatively prime natural numbers, then $φ (m n) = φ (m) φ (n)$ .
completely multiplicative function	No	It is not true for arbitrary natural numbers $m$ and $n$ that $φ (m n) = φ (m) φ (n)$ . For instance, if $m = n = 2$ , then $φ (m) = φ (n) = 1$ whereas $φ (m n)$ is 2.
divisibility-preserving function	Yes	If $m$ and $n$ are natural numbers such that $m$ divides $n$ , then $φ (m)$ divides $φ (n)$ .

Behavior

High and low points (relatively speaking)

Primes are high points: We also have $φ (n) \leq n - 1$ for $n > 1$ . Equality occurs if and only if $n$ is a prime number.
Primorials are low points: Roughly, the numbers occurring as primorials (products of the first few primes) have the lowest value of $φ (n)$ relative to $n$ , compared with other similarly sized numbers.

Measures of difference

We use the infinitude of primes for arguing about limit superiors.

Measure	Limit superior	Explanation	Limit inferior	Explanation
$φ (n) - n$	-1	maximum value of -1 occurs at primes	$- \infty$	Consider the sequence of powers 2. $φ (2^{k}) = 2^{k - 1}$ , so $φ (2^{k}) - 2^{k} = - 2^{k - 1} \to - \infty$ .
$\frac{φ (n)}{n}$	1	At each prime $p$ , value is $1 - (1 / p)$ . Limit is 1 as $p \to \infty$	0	Consider the sequence of primorials. The corresponding values of $φ (n) / n$ are products of the values $1 - (1 / p)$ for the first few primes $p$ . The limit of these is the infinite product $\prod_{p} (1 - \frac{1}{p})$ over all prime $p$ . This diverges because the infinite sum of the reciprocals of the primes diverges.
$\frac{\ln φ (n)}{\ln n}$	1	For each prime $p$ , the limit is $\ln (p - 1) / \ln p$ ,which approaches 1.	1	We can show that for every $ε > 0$ , there exists $N_{ε}$ such that $φ (n) \geq n^{1 - ε}$ for all $n \geq N_{ε}$ .

Summatory function and average value

Summatory function

The summatory function of the Euler phi-function is termed the totient summatory function.

Relation with other arithmetic functions

Similar functions

Universal exponent (also called Carmichael function) is the exponent of the multiplicative group modulo $n$ . The universal exponent of $n$ , usually denoted $λ (n)$ , divides $φ (n)$ .
Dedekind psi-function is similar tothe Euler phi-function, and is defined as:

$ψ (n) = n \prod_{p | n} (1 + \frac{1}{p})$ .

Relations expressed in terms of Dirichlet products

$φ * U = E$ : In other words, the Dirichlet product of the Euler phi-function and the all ones function is the identity function:

$\sum_{d | n} φ (d) = n$ .

$φ = E * μ$ : This is obtained by applying the Mobius inversion formula to the previous identity. The Euler phi-function is thus the Dirichlet product of the identity function and the Mobius function:

$\sum_{d | n} d μ (n / d) = φ (n)$ .

$φ * σ_{0} = σ$ : In other words, the Dirichlet product of the Euler phi-function and the divisor count function equals the divisor sum function:

$\sum_{d | n} φ (d) σ_{0} (n / d) = σ (n)$ .

$σ * φ = E * E$ .

Inequalities

$φ (n) \geq π (n) - ω (n)$ : Here, $π (n)$ is the prime-counting function, and counts the number of primes less than or equal to $n$ , while $ω (n)$ is the prime divisor count function of $n$ .
$φ (n) \leq n - σ_{0} (n) + 1$ : Here, $σ_{0} (n)$ is the divisor count function, counting the total number of divisors of $n$ .

Relation with properties of numbers

Prime number: A natural number $n$ such that $φ (n) = n - 1$ .
Polygonal number: A natural number $n$ such that $φ (n)$ is a power of $2$ , or equivalently, such that the regular $n$ -gon is constructible using straightedge and compass.

Dirichlet series

Further information: Formula for Dirichlet series of Euler phi-function

The Dirichlet series for the Euler phi-function is given by:

$\frac{φ (n)}{n^{s}}$ .

Using the Dirichlet product identity $φ * U = E$ and the fact that Dirichlet series of Dirichlet product equals product of Dirichlet series, we get:

$\sum_{n \in N} \frac{φ (n)}{n^{s}} \sum_{n \in m a t h b b N} \frac{1}{n^{s}} = \sum_{n \in N} \frac{n}{n^{s}}$ .

This simplifies to:

$\sum_{n \in m a t h b b N} \frac{φ (n)}{n^{s}} = \frac{ζ (s - 1)}{ζ (s)}$ .

This identity holds not just for the formal Dirichlet series, but also for their analytic continuations, and is valid universally for the meromorphic functions.

Algebraic significance

The Euler phi-function of $n$ is important in the following ways:

It is the number of generators of the cyclic group of order $n$ .
It is the order of the multiplicative group of the ring of integers modulo $n$ (in fact, this multiplicative group is precisely the set of generators of the additive group).