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

$\phi (n)=\prod _{i=1}^r{p}_i^{k_i}(1-\frac{1}{p_i})$.

In other words:

$\frac{\phi (n)}{n}=\prod _{i=1}^r(1-\frac{1}{p_i})$.

Behavior

Upper bound

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

Thus:

$limsup\frac{\varphi (p)}{p}=1$.

Lower bound

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

$\phi (n)\ge n^{1-ϵ}\mathrm{\forall }n\ge N_{ϵ}$.

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

$\phi (n)\ge n^{1-(C\log \log n/\log n)}$.

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

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

Relations expressed in terms of Dirichlet products

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

• $\phi =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)=\phi (n)$.

• $\phi *{\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}\phi (d){\sigma }_0(n/d)=\sigma (n)$.

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

Relation with properties of numbers

• Prime number: A number $n$ such that $\phi (n)=n-1$.

Properties

The Euler phi-function is a multiplicative function but not a completely multiplicative function.