What is Euler's Totient Function?

Suppose your friend wants to challenge you for an ice cream treat. They give you a number $n$, and they want you to find a number $m$ such that the greatest common divisor (GCD) of $n$ and $m$ is 1.

This is a fairly trivial task for you since you could say any prime number smaller than $n$ and win the challenge. But you want to impress your friend a little, and therefore announce that you could tell them the exact number of all such $m$ lying between $1$ and $n$ that satisfy the given condition.

Not believing you, your friend raises the stakes of the challenge, announcing that they will pay not only for ice cream but for the whole lunch you both just ate if you win.

Unlucky for your friend, you knew about the Euler's Totient Function, and since the given $n$ was quite small, you computed the answer in your mind and hence did not have to pay for the lunch.

Euler's totient function (also called phi-function or totient function) takes a single positive integer $n$ as input and outputs the number of integers present between $1$ and $n$ that are co-prime to $n$.

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:

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

Therefore,

Example 2

Let's take a bigger n, say 24. Factorizing it into pairs, we get:

Now considering the numbers from 1 to 23:

• 2, 3, 4, 6, 8, 12 completely divide 24 and therefore are not coprime to it.
• 9, 10, 14, 15, 16, 18, 20, 21, 22 have a common factor with 24 which is greater than 1, therefore these numbers are also not coprime to 24
• 1, 5, 7, 11, 13, 17, 19, 23 don't have any common factor other than 1 with 24, therefore, are co-prime to it.

The count of co-prime numbers to 24 (listed above) is 8. Therefore:

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

Having seen some examples, let's see how to calculate $\phi(n)$ for any arbitrary $n$. While describing the process, we might use some properties of the Totient function which you might not know. Don't worry about them, as we will see them later.

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,

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

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

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

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

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,

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

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

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

Explanation:

• The above implementation makes use of the result we derived in the last section. We initialize the answer with n, and then compute the remaining product.
• The for loop checks the divisibility of $n$ with all possible primes upto $\sqrt{n}$, and if that prime divides $n$, then divide with that prime until it is no longer divisible by it.
• Further, we multiply the answer with $\left(1-\frac{1}{p}\right)$. Please note that answer*(1-(1/p)) is mathematically equivalent to answer - (answer/p), but the latter part is not prone to precision errors that occur due to division of floating point numbers as being done in the former.
• Finally, if $n$ is still not $1$, then it must be the last prime factor of the original $n$. (It is due to the fact that there can be atmost $1$ prime factor of $m$ which is greater than $\sqrt{m}$). Thus, we include this last prime factor in our answer too.

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

C++ Implementation 2

Explanation:

• This implementation not only calculates the value of $\phi$ for just $n$, but also for all integers less than $n$.
• Factorizing all the numbers from $1$ to $n$ and then using the formula for each such number would be highly inefficient.
• Therefore, we use the idea of Sieve Of Erastothenes here. For each prime number in the list/array (checked by the clause phi[i]==i), we update all its multiples (present at phi[j]) by subtracting phi[j]/i from it.
• For all prime numbers themselves, only $1$ is subtracted from them. This is because phi[j]/i is equal to $1$ when phi[j] is equal to i. This is in accordance with the property 1 discussed below.

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

C++ Implementation 3 (Using Divisor Sum Property)

Explanation:

• This implementation uses the divisor sum property of the totient function (see property 4 below).
• Initially, we subtract $\phi(1)$ from all numbers since 1 divides all numbers, and therefore, we initialize the ith element of phi vector with i-1.
• Next, when we are at element i, we've already calculated phi[i] and the phi of all previous elements, and we will not update them any further.
• Now we subtract the value of phi[i] ($\phi$ of i) from all the multiples of i starting from 2*i which are less than n.
• When we've calculated uptil n, then our array phi contains the $\phi$ value of all numbers from $1$ to $n$

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

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

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