---
canonical_url: https://www.scaler.com/topics/eulers-totient-function/
title: Euler's Totient Function | Euler's Theorem - Scaler Topics
description: Learn about Eulers Totient Function by Scaler Topics. In this article, we will discuss Euler’s totient function, its applications, examples, etc.
author: Aman Kumar
category: Data Structures
amphtml: https://www.scaler.com/topics/eulers-totient-function/amp/
publish_date: 2022-03-02
---

:::section{.abstract}
## Overview
`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. It has a major application in `Euler's Theorem`.

:::

:::section{.tip}
**Note:**
1. Two 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.

:::

:::section{.main}
## 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.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
$$

:::

:::section{.main}
## 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,
$$
n = {p_1^{\alpha_1}} {\cdot} {p_2^{\alpha_2}} \cdots p_k^{\alpha_k}\tag{1}
$$

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

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

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

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

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

$$
\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}) \tag{3}
$$

---

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,

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

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

$$
\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}) \tag{5}
$$

---

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

:::

:::section{.main}
## 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)$

:::
:::section{.main}
## 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.

:::

:::section{.main}
## 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**.

:::

:::section{.summary}
## 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)$

:::