Euler’s Totient Function

Totient function (denoted by $\phi:\mathbb{N} \rightarrow \mathbb{N}$ ), also known as phi-function or Euler’s Totient function, is a mathematical function which counts the number of integers in the range $[1, n]$ (both inclusive) that are co-prime to $n$ or we can say whose GCD with n is 1.

Note:

1. 2 positive integers a and b are said to be co-prime if their greatest common factor/divisor is equal to 1, that is,

$$
\gcd(a, b) = 1
$$

2. $1$ is considered co-prime to all numbers.

Example of Euler's Totient Function

Example 1

For an small example, let’s take $n = 10$.

The numbers less than 10 are as follows:

$$
1, 2, 3, 4, 5, 6, 7, 8, 9
$$

Out of these,

• 1 is co-prime to 10 (by definition).
• 2 and 5 completely divide 10, therefore, are not co-prime to 10.
• 4, 6, 8 are divisible by 2 (just like 10), therefore, their greatest common divisor is 2. Therefore, they are also not coprime to 10..
• 3, 7, 9 neither divide 10 nor share any common factor with it. Therefore, by definition of coprime numbers, we saw earlier, these numbers are coprime to 10.

Therefore, there are 4 numbers less than 10 that are co-prime to it. These are

$$
1, 3, 7, 9
$$

Therefore,

$$
\phi(10) = 4
$$

Example 2

Let’s take a bigger n, say 24.

In range [1,24] there are total 8 numbers 1,5,7,11,13,17,19,23 are there whose gcd with 24 is equal to 1 (they are coprime to it). Therefore:
$$
\phi(n) = 8
$$

How to Compute Φ(n) for an Input n?

Suppose you’re given an integer $n \in \mathbb{N}$. Using the fundamental theorem of arithmetic, we know that $n$ can be decomposed as a product of the positive integral powers of its prime factors. Therefore,

(1):
$$
n = {p_1^{\alpha_1}} {\cdot} {p_2^{\alpha_2}} \cdots p_k^{\alpha_k}
$$

where $p_i$ are prime factors of $n$.

Now using an interesting property of the totient function, which states that

(2):

$$
\phi(abc) = \phi{a}\cdot\phi(b)\cdot\phi(c)
$$

provided that $a, b, c$ are co-prime to each other.

Using $(1)$ and $(2)$, we get

(3):
$$
\phi(n) = \phi({p_1^{\alpha_1}} {\cdot} {p_2^{\alpha_2}} \cdots p_k^{\alpha_k}) = \phi(p_1^{\alpha_1})\cdot\phi(p_2^{\alpha_2})\cdots\phi(p_k^{\alpha_k})
$$

Another interesting property of the totient function $\phi(m)$ is that if $m$ is a power of a prime number, say $p^{\alpha}$ where $\alpha \ge 1$, then,

(4):
$$
\phi(m) = \phi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1}
$$

Using $(4)$ and $(3)$, we get

(5):
$$
\phi(n) = (p_1^{\alpha_1}-p_1^{\alpha_1-1})\cdot(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdot(p_3^{\alpha_3}-p_3^{\alpha_3-1})\cdots(p_k^{\alpha_k}-p_k^{\alpha_k-1})
$$

Taking $p_i^{\alpha_i}$ common from $i^{th}$ term from RHS of $(5)$, we get

$$
={p_1^{\alpha_1}} {\cdot} {p_2^{\alpha_2}} \cdots p_k^{\alpha_k}\cdot \left(1 – \frac{1}{p_1}\right) \cdot\left(1 – \frac{1}{p_2}\right) \cdots \left(1 – \frac{1}{p_k}\right)
$$

$$
= n \cdot \left(1 – \frac{1}{p_1}\right) \cdot \left(1 – \frac{1}{p_2}\right) \cdots \left(1 – \frac{1}{p_k}\right)
$$

Hence we get
$$
\phi(n) = n \cdot \left(1 – \frac{1}{p_1}\right) \cdot \left(1 – \frac{1}{p_2}\right) \cdots \left(1 – \frac{1}{p_k}\right)
$$

The above equation gives us a method to calculate $\phi(n)$ for any desired $n$.

Code Implementation

Using the result we derived above, it is quite easy to write a program to calculate $\phi(n)$ for an input $n$.

C++ Implementation 1

long long phi(long long n) 
{
    long long answer = n;

    for (long long p = 2; p * p <= n; p++) 
    {
        if (n % p == 0) 
        {
            while (n % p == 0)
            {
                n = n/p;
            }
            answer = answer-(answer / p);
        }
    }

    if (n > 1)
    {
        answer = answer-(answer / n);
    }
    return answer;
}

Explanation:

The algorithm initializes answer with n and iterates through primes up to the square root of n, dividing n by each prime divisor found. It updates answer by multiplying it with (1 – 1/p), ensuring accuracy. If n remains greater than 1 after this process, it accounts for the last prime factor of n. This optimized approach efficiently calculates Euler’s Totient function, addressing precision errors by using multiplication instead of division.

Time Complexity: $\mathcal{O}({\sqrt{n}})$

Space Complexity: $\mathcal{O}(1)$

C++ Implementation 2

vector<long long> phi_n(long long n) 
{
    vector<long long> phi(n + 1);

    phi[0] = 0;
    phi[1] = 1;

    for (long long i = 2; i <= n; i++)
    {
        phi[i] = i;
    }

    for (int i = 2; i <= n; i++) 
    {
        if (phi[i] == i) 
        {
            for (int j = i; j <= n; j += i)
            {
                phi[j] -= phi[j] / i;
            }
        }
    }

    return phi;
}

Explanation:
This optimized implementation efficiently computes Euler’s totient function ($\phi$) for all integers up to $n$ using the Sieve of Eratosthenes. Rather than factorizing each number individually, it iterates through primes and updates their multiples by subtracting $\phi[j]/i$. For prime numbers, it subtracts 1. This approach ensures efficiency by avoiding redundant computations.

Time Complexity: $\mathcal{O}(n\log(\log{n}))$

Space Complexity: $\mathcal{O}(n)$

C++ Implementation 3 (Using Divisor Sum Property)

vector<long long> phi_n(long long n) 
{
    vector<long long> phi(n + 1);
    phi[0] = 0;
    phi[1] = 1;
    for (long long i = 2; i <= n; i++)
    {
        phi[i] = i - 1;
    }

    for (long long i = 2; i <= n; i++)
    {
        for (long long j = 2 * i; j <= n; j += i)
        {
              phi[j] -= phi[i];
        }
    }

    return phi;
}

Explanation:
This implementation leverages the divisor sum property of the totient function. Initially, subtracting ϕ(1) from all numbers, the ith element of the phi vector initializes as i-1. When processing element i, previous phi values remain unchanged. Subsequently, phi[i] subtracts from multiples of i starting from 2*i up to n. Upon completion, the phi array holds the ϕ values for numbers 1 to n. This optimized approach efficiently computes totient values, exploiting the properties of integer factorization.

Time Complexity: $\mathcal{O}(n\log{(n)})$

Space Complexity: $\mathcal{O}(n)$

Properties of Euler's Totient Function

In addition to the above-used properties, we also have the following results related to the Totient function:

1. If $p$ is a prime number, then
   $$
   \phi(p) = p-1
   $$
2. If $p$ is a prime number and $m$ is a positive integer (that is, $m \ge 1$), then
   $$
   \phi(p^m) = p^{m}-p^{m-1}
   $$
3. For any two positive integers $m$ and $n$ we have
   $$
   \phi(mn) = \phi(m)\cdot\phi(n)\cdot \frac{\gcd(m, n)}{\phi(\gcd(m, n))}
   $$ Considering the case when $m$ and $n$ are coprime, then $\gcd(m,n)=1$. In such a scenario, the above relation reduces to
   $$
   \phi(mn) = \phi(m)\cdot\phi(n)
   $$
4. The sum of values of the totient function over the positive divisors of $n$ equals $n$ itself. In other words:
   $$
   \sum_{k|n} \phi{(k)} = n
   $$
5. If $m$ and $n$ are two prime numbers, then using (1) and (3), we get:
   $$
   \phi(mn) = \phi(m)\cdot\phi(n) = (m-1)\cdot(n-1)
   $$ This property is used in the RSA algorithm.

Application of Totient Function in Euler's Theorem

Euler's theorem (sometimes also called as Euler’s totient theorem) which makes use of Euler’s totient function, states the following:

If $a$, $n$ $\in \mathbb{N}$ are relatively prime, then
$$
a^{\phi(n)} \equiv 1\mod{n}
$$

The converse of the Euler's theorem also holds, which is stated as:

If $a^{\phi(n)} \equiv 1 \mod{n}$, then $a$ and $n$ are relatively prime.

A special case of this theorem where $n$ is a prime number is used in the RSA encryption algorithm. This special case of the theorem is popularly known as Fermat's Little Theorem and states that

$a^{n-1} \equiv 1 \mod{n}$

Taking an example, suppose $a = 10$ and $n = 9$. Using the methods described above, we get $\phi(9) = 6$.

Therefore, $a^{\phi(n)} = 10^{6}$.

Applying the $\mod n \ (=\mod 9)$ operator on $10^6$, we get
$$
10^6\mod9= (11111\times9+1)\mod9
= 0 + (1\mod9) = 1
$$

which was the expected result since 10 and 9 don’t have any common divisor other than 1, that is to say, they are co-prime.

Suppose we had taken a number $n = 2$ which is not co-prime to 10 (since their greatest common divisor is 2).

In this case, $\phi(n)= \phi(2) =1$.

Therefore, $a^{\phi(n)} = 10^{1} = 10$.

Applying the $\mod n \ (=\mod 2)$ operator on $10$, we get
$$
10\mod2= (5\times2)\mod2
= 0 \neq 1
$$

Thus, we’ve verified that the theorem does not hold when $a$ and $n$ are not co-prime.

Conclusion

1. Euler's totient function, $\phi:\mathbb{N} \rightarrow \mathbb{N}$, counts the number of integers between $1$ and $n$ (both inclusive) that are co-prime to $n$.
2. If $p$ is a prime number, then
   $$
   \phi(p) = p-1
   $$
3. The sum of values of the totient function over the positive divisors of $n$ equals $n$ itself.
4. Totient Function is used in Euler’s theorem, Fermat’s Little theorem which is used in the RSA encryption algorithm.
5. The value of Totient function for a number $n$ can be implemented in the best time complexity of $\mathcal{O}(n\log{(\log{n})})$ with an associated space complexity of $\mathcal{O}(n)$