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

Behavior

Upper bound

The largest values of $\phi (n)$ are taken when $n$ is prime. $\phi (p)=p-1$ for a prime $p$ .

Thus:

$\lim \sup {\frac {\phi (p)}{p}}=1$ .

Lower bound

For any $\epsilon >0$ , there exists $N_{\epsilon }$ such that:

$\varphi (n)\geq n^{1-\epsilon }\ \forall \ n\geq N_{\epsilon }$ .

With the prime number theorem, we can find a constant $C$ such that:

Failed to parse (unknown function "\logn"): {\displaystyle \varphi(n) \ge n^{1 - (C\log\log n/\logn)}} .

Relation with other arithmetic 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)$ .

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 *\tau =\sigma$ : In other words, the Dirichlet product of the Euler phi-function and the divisor count function equals the divisor sum function: