Euler's totient function

• 05 June 2025
• cryptography,
• group theory,
• number theory

Euler's totient function, denoted $\varphi (n)$, counts the positive integers up to a given integer $n$ that are relatively prime to $n$, meaning their greatest common divisor with $n$ is 1.

The precise definition states that for any positive integer $n$, the value of $\varphi (n)$ equals the number of integers $k$ in the range $1\le k\le n$ such that $gcd(k,n)=1$.

Take a prime number $p$. All positive integers less than $p$ are relatively prime to $p$.

$$\therefore \varphi (p)=p-1$$

For a prime power $p^a$, where $p$ is prime and $a$ is a positive integer, the totient function is:

$$\varphi (p^a)=p^a-p^{a-1}=p^a(1-\frac{1}{p})$$

This only arises because among the numbers from 1 to $p^a$, exactly those that are divisible by $p$ are not relatively prime to $p^a$. There are $p^{a-1}$ such numbers.

One of the most valuable properties of Euler's totient function is its multiplicativity.

If $m$ and $n$ are coprime (i.e. $gcd(m,n)=1$), then:

$$\varphi (mn)=\varphi (m)\times \varphi (n)$$

This let's us compute $\varphi (n)$ for any integer $n$ by first finding its prime factorization. Given $n=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}$, where each $p_i$ is a distinct prime, we have:

$$\varphi (n)=\varphi (p_1^{a_1})\times \varphi (p_2^{a_2})\times \cdots \times \varphi (p_k^{a_k})$$

Substituting the formula for prime powers, we get:

$$\varphi (n)=p_1^{a_1}(1-\frac{1}{p_1})\times p_2^{a_2}(1-\frac{1}{p_2})\times \cdots \times p_k^{a_k}(1-\frac{1}{p_k})$$

Which simplifies to:

$$\varphi (n)=n\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2})\times \cdots \times (1-\frac{1}{p_k})$$

The time complexity of computing $\varphi (n)$ depends on the algorithm. Using the formula above requires finding the prime factorization of $n$, which has a time complexity of $O(n^{1/4})$ using the general number field sieve (GNFS) for large integers.

Although, for practical purposes with reasonably sized numbers, the complexity is expressed as $O(\sqrt{n})$ using trial division methods.

The space complexity for computing $\varphi (n)$ is $O(\log n)$ as we need to store the prime factorization of $n$.

Euler's totient function appears in several important theorems in number theory. One of the most significant is Euler's theorem, which states that if $a$ and $n$ are coprime, then:

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

This is a generalization of Fermat's Little Theorem, which states that if $p$ is prime and $a$ is not divisible by $p$, then:

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

Note that for a prime $p$, we have $\varphi (p)=p-1$, which aligns the two theorems.

In RSA, the security relies on the difficulty of factoring large composite numbers. The encryption and decryption operations use modular exponentiation, with the decryption key $d$ satisfying:

$$ed\equiv 1(\mathrm{mod}\varphi (n))$$

Where $e$ is the encryption key and $n$ is the product of two large primes.

The computational complexity of modular exponentiation used in RSA is $O({\log }^{3}n)$ using the square-and-multiply algorithm which is way faster than attempting to factor $n$ to find $\varphi (n)$ directly.

Another important result of $\varphi (n)$ is the formula for the sum of $\varphi (d)$ over all divisors $d$ of $n$:

$$\sum _{d|n}\varphi (d)=n$$

It's an elegant result that relates the totient function and the structure of integer divisors.

E.g. let's compute this sum for $n=12$:

• The divisors of 12 are: 1, 2, 3, 4, 6 and 12
• $\varphi (1)=1$
• $\varphi (2)=1$
• $\varphi (3)=2$
• $\varphi (4)=2$
• $\varphi (6)=2$
• $\varphi (12)=4$
• Sum: $1+1+2+2+2+4=12$

As predicted, the sum equals $n=12$.

The Möbius inversion formula provides a way to express $\varphi (n)$ in terms of the Möbius function $\mu (n)$.

$$\varphi (n)=\sum _{d|n}\mu (d)\cdot \frac{n}{d}$$

The Möbius function $\mu (n)$ is defined as:

• $\mu (1)=1$
• $\mu (n)=0$ if $n$ has a squared prime factor
• $\mu (n)=(-1{)}^k$ if $n$ is the product of $k$ distinct primes

Computing $\varphi (n)$ using this approach has a time complexity of $O(n\log \log n)$ if we precompute the Möbius function using the sieve of Eratosthenes.

Euler's totient function also appears in the context of cyclotomic polynomials. The $n$-th cyclotomic polynomial, denoted ${\mathrm{\Phi }}_n(x)$, is the minimal polynomial over the rational numbers of the primitive $n$-th roots of unity. The degree of ${\mathrm{\Phi }}_n(x)$ is precisely $\varphi (n)$.

For example, ${\mathrm{\Phi }}_1(x)=x-1$ and $\varphi (1)=1$, confirming that the degree is $\varphi (1)$.

The totient function satisfies several interesting identities and inequalities.

$$\varphi (n)\ge \sqrt{n/2}\text{for}n>6$$

The average order of the totient function is:

$$\frac{1}{n}\sum _{k=1}^n\varphi (k)\sim \frac{3n}{{\pi }^2}\approx \frac{3n}{10}$$

This means that as $n$ grows, the average value of $\varphi (k)$ for $k$ from 1 to $n$ approaches $\frac{3n}{{\pi }^2}$.

Computing $\varphi (n)$ for a large range of values can be done using the sieve method. If we want to compute $\varphi (k)$ for all $k$ from 1 to $n$, the time complexity is $O(n\log \log n)$ and the space complexity is $O(n)$.

The algorithm proceeds as follows:

1. Initialize an array $\varphi [1...n]$ with $\varphi [i]=i$ for all $i$
2. For each prime $p$ from 2 to $n$:
   • If $\varphi [p]=p$ (meaning $p$ is still marked as a prime):
     • Subtract $\varphi [j]$ by $\varphi [j]/p$ for all multiples $j$ of $p$ up to $n$

This applies $\varphi (n)=n\prod _{p|n}(1-\frac{1}{p})$ to all numbers simultaneously.

Let's compute some values of $\varphi (n)$ for small $n$.

• $\varphi (1)=1$ (only 1 is coprime to 1)
• $\varphi (2)=1$ (only 1 is coprime to 2)
• $\varphi (3)=2$ (1 and 2 are coprime to 3)
• $\varphi (4)=2$ (1 and 3 are coprime to 4)
• $\varphi (5)=4$ (1, 2, 3 and 4 are coprime to 5)
• $\varphi (6)=2$ (1 and 5 are coprime to 6)

The Chinese Remainder Theorem (CRT) is closely related to Euler's totient function. CRT states that if $m_1,m_2,\dots ,m_k$ are pairwise coprime positive integers, then the system of congruences:

$$\begin{array}{rl}x& \equiv a_1(\mathrm{mod}{m}_1)\\ x& \equiv a_2(\mathrm{mod}{m}_2)\\ & ⋮\\ x& \equiv a_k(\mathrm{mod}{m}_k)\end{array}$$

has a unique solution modulo $M=m_1\times m_2\times \cdots \times m_k$.

The number of solutions to the congruence $x^2\equiv 1(\mathrm{mod}n)$ is related to the prime factorization of $n$ and can be expressed in terms of $\varphi (n)$ for certain types of $n$.

In group theory, if $G$ is a finite abelian group, then the number of elements of order $n$ in $G$ is either 0 or $\varphi (n)$. This is useful in the study of the multiplicative group of integers modulo $n$, denoted $(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$, which has order $\varphi (n)$.

For prime $p$, the multiplicative group $(\mathbb{Z}/p\mathbb{Z}{)}^{\ast }$ is cyclic of order $\varphi (p)=p-1$. A generator of this group is called a primitive root modulo $p$.

The complexity of finding a primitive root modulo $p$ is $O((\log p{)}^4)$ using deterministic algorithms or $O((\log p{)}^2)$ using probabilistic algorithms.

Euler's totient function is also related to the Carmichael function $\lambda (n)$, which gives the smallest positive integer $m$ such that $a^m\equiv 1(\mathrm{mod}n)$ for all integers $a$ coprime to $n$. The Carmichael function always divides $\varphi (n)$ and equals $\varphi (n)$ when $n$ is 1, 2, 4, a power of an odd prime or twice a power of an odd prime.

In the context of computational number theory, algorithms for computing $\varphi (n)$ can be optimized using various techniques. E.g. if we have access to the prime factorization of $n$, we can compute $\varphi (n)$ in $O(k)$ time where $k$ is the number of distinct prime factors of $n$.

Research on the distribution of values of $\varphi (n)$ has revealed interesting patterns. E.g. $\varphi (a)=\varphi (b)$ can have multiple solutions, meaning there exist distinct integers that share the same totient value. The smallest such pair is $(a,b)=(4,6)$ since $\varphi (4)=\varphi (6)=2$.

The totient function has connections to perfect numbers as well. A perfect number is equal to the sum of its proper divisors. If $2^p-1$ is prime (making it a Mersenne prime), then $n=2^{p-1}(2^p-1)$ is a perfect number and $\varphi (n)=2^{p-1}(2^p-1-1)=2^{p-1}(2^p-2)=2^p(2^{p-1}-1)$.

• ← Previous
  Linking object files
• Next →
  Linux syscalls