`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:**

- 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

$$

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

:

- If $p$ is a
`prime number`

, then

$$

\phi(p) = p-1

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

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

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

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

`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$.- If $p$ is a
`prime number`

, then

$$

\phi(p) = p-1

$$ - The sum of values of the totient function over the positive divisors of $n$ equals $n$ itself.
- Totient Function is used in Euler’s theorem, Fermat’s Little theorem which is used in the RSA encryption algorithm.
- 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)$