1.
Introduction:
2.
Approach 1:
3.
Approach 2:
4.
Approach 3:
5.
FAQs:
6.
Key Takeaways:
Last Updated: Mar 27, 2024

Euler’s Totient Function

Nishant Rana
0 upvote

Introduction:

Euler’s totient function counts the total numbers between 1 to N, which are coprime to ‘N’. Two numbers are said to be coprime if the G.C.D.(Greatest Common Divisor) of both the numbers is 1.

1 is coprime to all the numbers.

Euler’s Totient function is also known as phi-function ϕ(N).

The above table shows the ϕ(N) value for the first few N values.

Let us see a few properties of the Euler’s Totient Function:-

1. If a number(let us say ‘p’) is prime then gcd of ‘p’ with any number less than ‘p’ i.e. 1 <= q < p is equal to 1.
gcd(p, q) = 1
Hence, ϕ(p) = p - 1.
2. If ‘p’ is a prime number, then there are exactly p/ p numbers between 1 and pk that are divisible by p.
Hence, ϕ(pk) = pk - pk - 1.
3. If ‘a’ and ‘b’ are relatively prime then ϕ(ab) = ϕ(a) * ϕ(b).
This relation is derived from the Chinese remainder theorem.

Approach 1:

We can calculate the value of ϕ(N) using the above points by factorizing ‘N’.

Let us say N = (p1a1) * (p2a2) * (p3a3) * (p4a4)...........* (p5a5) where pis a prime factor of ‘N’.

-> ϕ(N) = ϕ(p1a1) * ϕ(p2a2) * ϕ(p3a3) * ϕ(p4a4)...........* ϕ(pkak)

->         = (p1a1 - p1a1-1) * (p2a2 - p1a2-1) * (p3a3 - p1a3-1)...........* (pkak - pkak-1)

->         = p1a1 * (1 - 1/p1) * p2a2 * (1 - 1/p2) * p3a3 * (1 - 1/p3).......* pkak * (1 - 1/pk)

->       = N * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3).......* (1 - 1/pk)

Let us implement the above approach:

Output:

Time Complexity: The time complexity of the above approach is O(√N) because we are running an O(√N) for loop only.

Space Complexity: The space complexity for the above approach is O(1) because we are using constant auxiliary space.

Also see, Euclid GCD Algorithm

Approach 2:

We can optimize the above approach for Euler’s Totient by efficiently calculating the prime factors of a number. We can use the Sieve of Eratosthenes to efficiently calculate the factors of a number. Instead of updating the temporary result for each prime factor for each number, we find all prime numbers. For each one, update the temporary results of all numbers divisible by that prime number.

Output:

Time Complexity: The time complexity of the above approach is O(N * log(log(N))) because we are applying a similar approach to the Sieve of Eratosthenes.

Space Complexity: The space complexity for the above approach is O(N) because we are maintaining a ‘phi’ array of size ‘N’.

Read More - Time Complexity of Sorting Algorithms

Approach 3:

There is one interesting property by Gauss:

∑ϕ(d) = N

d|n

Here the sum is over all positive divisors ‘d’ of ‘N’.

Let us say N = 12.

Divisors of N are 1, 2, 3, 4, 6, 12

Hence, ϕ(1) + ϕ(2) + ϕ(3) + ϕ(4) + ϕ(6) + ϕ(12) = 1 + 1 +2 + 2 + 2 + 4 = 12

Using the above property we can also implement the Euler’s Totient function.

Output:

Time Complexity: The time complexity for the above approach is O(N * log(N)) because we are running two nested for loops. The outer for loop runs in O(N) time and the inner for loop takes O(log(N)) time.

Space Complexity: The space complexity for the above approach is O(N) because we are maintaining a ‘phi’ array of size ‘N’.

FAQs:

1. What is Euler’s Totient function?
• Euler’s totient function counts the total numbers between 1 to N, which are coprime to ‘N.’ Two numbers are said to be coprime if the G.C.D.(Greatest Common Divisor) of both the numbers is 1.

2.What is the most time-optimized approach to implement Euler’s totient function?

• The most time-optimized approach for the Euler’s totient function is O(n * log(log(n))) which we implement using Sieve of Eratosthenes.

Key Takeaways:

In this blog, we have covered the following things:

1. We first discussed what Euler’s totient function is.
2. Then we discussed the different implementations for Euler’s totient function.

If you want to learn more about Number Theory and want to practice some questions which require you to take your basic knowledge on Number Theory a notch higher, then you can visit our Guided Path for Number Theory

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass