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 _{n\to \infty }{\frac {\phi (n)}{n}}=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:

$\varphi (n)\geq n^{1-(C\log \log n/\log 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 $\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.

Properties

Multiplicativity

This arithmetic function is a multiplicative function: the product of this function for two natural numbers that are relatively prime is the value of the function at the product.
View a complete list of multiplicative functions

Complete multiplicativity

NO: This arithmetic function is not a completely multiplicative function: in other words, the product of the values of the function at two natural numbers need not equal the value at the product.

Preservation of divisibility

This arithmetic function is a divisibility-preserving function: if one natural number divides another, the value of the function at the first number also divides the value at the second number.
View other divisibility-preserving functions

If $m$ divides $n$, then $\varphi (m)$ divides $\varphi (n)$.

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