Euler's Totient Function | Euler's Theorem

Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

Totient function (denoted by ϕ:NN\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][1, n] (both inclusive) that are co-prime to nn 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\gcd(a, b) = 1
  1. 11 is considered co-prime to all numbers.

Example of Euler's Totient Function

Example 1

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

The numbers less than 10 are as follows:

1,2,3,4,5,6,7,8,91, 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,91, 3, 7, 9

Therefore,

ϕ(10)=4\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:

ϕ(n)=8\phi(n) = 8

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

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

(1):

n=p1α1p2α2pkαkn = {p_1^{\alpha_1}} {\cdot} {p_2^{\alpha_2}} \cdots p_k^{\alpha_k}

where pip_i are prime factors of nn.

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

(2):

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

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

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

(3):

ϕ(n)=ϕ(p1α1p2α2pkαk)=ϕ(p1α1)ϕ(p2α2)ϕ(pkαk)\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 ϕ(m)\phi(m) is that if mm is a power of a prime number, say pαp^{\alpha} where α1\alpha \ge 1, then,

(4):

ϕ(m)=ϕ(pα)=pαpα1\phi(m) = \phi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1}

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

(5):

ϕ(n)=(p1α1p1α11)(p2α2p2α21)(p3α3p3α31)(pkαkpkαk1)\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 piαip_i^{\alpha_i} common from ithi^{th} term from RHS of (5)(5), we get

=p1α1p2α2pkαk(11p1)(11p2)(11pk)={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(11p1)(11p2)(11pk)= 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

ϕ(n)=n(11p1)(11p2)(11pk)\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 ϕ(n)\phi(n) for any desired nn.

Code Implementation

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

C++ Implementation 1

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: O(n)\mathcal{O}({\sqrt{n}})

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


C++ Implementation 2

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

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

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


C++ Implementation 3 (Using Divisor Sum Property)

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: O(nlog(n))\mathcal{O}(n\log{(n)})

Space Complexity: O(n)\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 pp is a prime number, then

    ϕ(p)=p1\phi(p) = p-1
  2. If pp is a prime number and mm is a positive integer (that is, m1m \ge 1), then

    ϕ(pm)=pmpm1\phi(p^m) = p^{m}-p^{m-1}
  3. For any two positive integers mm and nn we have

    ϕ(mn)=ϕ(m)ϕ(n)gcd(m,n)ϕ(gcd(m,n))\phi(mn) = \phi(m)\cdot\phi(n)\cdot \frac{\gcd(m, n)}{\phi(\gcd(m, n))}

    Considering the case when mm and nn are coprime, then gcd(m,n)=1\gcd(m,n)=1. In such a scenario, the above relation reduces to

    ϕ(mn)=ϕ(m)ϕ(n)\phi(mn) = \phi(m)\cdot\phi(n)
  4. The sum of values of the totient function over the positive divisors of nn equals nn itself. In other words:

    knϕ(k)=n\sum_{k|n} \phi{(k)} = n
  5. If mm and nn are two prime numbers, then using (1) and (3), we get:

    ϕ(mn)=ϕ(m)ϕ(n)=(m1)(n1)\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 aa, nn N\in \mathbb{N} are relatively prime, then

aϕ(n)1modna^{\phi(n)} \equiv 1\mod{n}

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

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

A special case of this theorem where nn 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

an11modna^{n-1} \equiv 1 \mod{n}


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

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

Applying the modn (=mod9)\mod n \ (=\mod 9) operator on 10610^6, we get

106mod9=(11111×9+1)mod9=0+(1mod9)=110^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=2n = 2 which is not co-prime to 10 (since their greatest common divisor is 2).

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

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

Applying the modn (=mod2)\mod n \ (=\mod 2) operator on 1010, we get

10mod2=(5×2)mod2=0110\mod2= (5\times2)\mod2 = 0 \neq 1

Thus, we've verified that the theorem does not hold when aa and nn are not co-prime.

Conclusion

  1. Euler's totient function, ϕ:NN\phi:\mathbb{N} \rightarrow \mathbb{N}, counts the number of integers between 11 and nn (both inclusive) that are co-prime to nn.
  2. If pp is a prime number, then
    ϕ(p)=p1\phi(p) = p-1
  3. The sum of values of the totient function over the positive divisors of nn equals nn 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 nn can be implemented in the best time complexity of O(nlog(logn))\mathcal{O}(n\log{(\log{n})}) with an associated space complexity of O(n)\mathcal{O}(n)