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 $\varphi (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:

$\varphi (n)=\prod _{i=1}^{r}p_{i}^{k_{i}}\left(1-{\frac {1}{p_{i}}}\right)$.

In other words:

${\frac {\varphi (n)}{n}}=\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right)$.

Properties

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

Behavior

High and low points (relatively speaking)

• Primes are high points: We also have $\varphi (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 $\varphi (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
$\varphi (n)-n$	-1	maximum value of -1 occurs at primes	$-\infty$	Consider the sequence of powers 2. $\varphi (2^{k})=2^{k-1}$, so $\varphi (2^{k})-2^{k}=-2^{k-1}\to -\infty$.
${\frac {\varphi (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 $\varphi (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}\left(1-{\frac {1}{p}}\right)$ over all prime $p$. This diverges because the infinite sum of the reciprocals of the primes diverges.
${\frac {\ln \varphi (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 $\varepsilon >0$, there exists $N_{\varepsilon }$ such that $\varphi (n)\geq n^{1-\varepsilon }$ for all $n\geq N_{\varepsilon }$.

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 $\lambda (n)$, divides $\varphi (n)$.
• Dedekind psi-function is similar tothe Euler phi-function, and is defined as:

$\psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right)$.

Relations expressed in terms of Dirichlet products

• $\varphi *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}\varphi (d)=n$.

• $\varphi =E*\mu$: 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\mu (n/d)=\varphi (n)$.

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

$\sum _{d|n}\varphi (d)\sigma _{0}(n/d)=\sigma (n)$.

• $\sigma *\varphi =E*E$.

Inequalities

• $\varphi (n)\geq \pi (n)-\omega (n)$: Here, $\pi (n)$ is the prime-counting function, and counts the number of primes less than or equal to $n$, while $\omega (n)$ is the prime divisor count function of $n$.
• $\varphi (n)\leq n-\sigma _{0}(n)+1$: Here, $\sigma _{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 $\varphi (n)=n-1$.
• Polygonal number: A natural number $n$ such that $\varphi (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 {\varphi (n)}{n^{s}}}$.

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

$\sum _{n\in \mathbb {N} }{\frac {\varphi (n)}{n^{s}}}\sum _{n\in mathbb{N}}{\frac {1}{n^{s}}}=\sum _{n\in \mathbb {N} }{\frac {n}{n^{s}}}$.

This simplifies to:

$\sum _{n\in mathbb{N}}{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (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).