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. The limits discussed are in the limit as $n \to \infty$ . Note that the last quotient is undefined for $n = 1$ .

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_{ε}$ .

Related arithmetic functions

Summatory functions

The sum of the values of the totient function for all natural numbers up to a given number is termed the totient summary function.

Similar functions

Name of arithmetic function Description Mathematical relation with Euler totient function

Universal exponent (also called Carmichael function) The exponent of the multiplicative group modulo $n$ . Denoted $λ (n)$ $λ (n)$ divides $φ (n)$ . This is related to the group-theoretic fact that exponent divides order.

Dedekind psi-function

Defined as

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

Structural similarity in definition. Also,

ψ (n) \geq φ (n)

for all

n

, with equality occurring iff

n = 1

.

Relations expressed in terms of Dirichlet products

Below are some Dirichlet products of importance.

Statement	Function	Value of the Dirichlet product $φ *$ the function	Description	Statement in ordinary notation	Proof	Corollaries
$φ * U = E$	$U$	the function that sends every natural number to 1	$E$	the function that sends every natural number to itself	$\sum_{d \| n} φ (d) = n$	Direct combinatorial argument: each summand is the number of elements in ${1, \dots, n}$ whose gcd with $n$ with $n / d$ .	$φ = E * μ$ , where $μ$ is the Mobius function. This follows from the fact that $μ = U^{- 1}$ . Also, $φ * σ_{1} = E * E$ , follows from this and $σ_{1} = E * U$ .
$φ * σ_{0} = σ_{1}$	$σ_{0} < m a t h > \| \| t h e [[d i v i s o r c o u n t f u n c t i o n]] < m a t h > σ = σ_{1}$	the divisor sum function	$\sum_{d \| n} φ (d) σ_{0} (n / d) = σ (n)$	Proof: We have $σ_{0} = U * U$ and $σ_{1} = E * U$ by definition. Multiply both sides of the former by $φ$ and use associativity to get $φ * σ_{0} = (φ * U) * U$ . Use the preceding identity to get $φ * σ_{0} = E * U$ , so $φ * σ_{0} = σ_{1}$ .

The table of relationships can be conceptualized as follows, where the cell entries are the products of their row and column headers:

	$μ = U^{- 1}$ (Mobius function)	$I$ (Kronecker delta with 1, identity for Dirichlet product)	$U$ (all ones function)	$σ_{0} = U^{2}$ (divisor count function)
$E$ (identity map, sends everything to itself)	$φ$	$E$	$σ_{1}$	no name

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).