Euler's Totient Function | Euler's Theorem
Totient function (denoted by ), also known as phi-function or Euler's Totient function, is a mathematical function which counts the number of integers in the range (both inclusive) that are co-prime to 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,
- is considered co-prime to all numbers.
Example of Euler's Totient Function
Example 1
For an small example, let's take .
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.
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:
How to Compute Φ(n) for an Input n?
Suppose you're given an integer . Using the fundamental theorem of arithmetic, we know that can be decomposed as a product of the positive integral powers of its prime factors. Therefore,
(1):
where are prime factors of .
Now using an interesting property of the totient function, which states that
(2):
provided that are co-prime to each other.
Using and , we get
(3):
Another interesting property of the totient function is that if is a power of a prime number, say where , then,
(4):
Using and , we get
(5):
Taking common from term from RHS of , we get
Hence we get
The above equation gives us a method to calculate for any desired .
Code Implementation
Using the result we derived above, it is quite easy to write a program to calculate for an input .
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:
Space Complexity:
C++ Implementation 2
Explanation: This optimized implementation efficiently computes Euler's totient function () for all integers up to using the Sieve of Eratosthenes. Rather than factorizing each number individually, it iterates through primes and updates their multiples by subtracting . For prime numbers, it subtracts 1. This approach ensures efficiency by avoiding redundant computations.
Time Complexity:
Space Complexity:
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:
Space Complexity:
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 is a prime number, then
-
If is a prime number and is a positive integer (that is, ), then
-
For any two positive integers and we have
Considering the case when and are coprime, then . In such a scenario, the above relation reduces to
-
The sum of values of the totient function over the positive divisors of equals itself. In other words:
-
If and are two prime numbers, then using (1) and (3), we get:
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 , are relatively prime, then
The converse of the Euler's theorem also holds, which is stated as:
If , then and are relatively prime.
A special case of this theorem where 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
Taking an example, suppose and . Using the methods described above, we get .
Therefore, .
Applying the operator on , 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 which is not co-prime to 10 (since their greatest common divisor is 2).
In this case, .
Therefore, .
Applying the operator on , we get
Thus, we've verified that the theorem does not hold when and are not co-prime.
Conclusion
- Euler's totient function, , counts the number of integers between and (both inclusive) that are co-prime to .
- If is a prime number, then
- The sum of values of the totient function over the positive divisors of equals 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 can be implemented in the best time complexity of with an associated space complexity of