Euler's Totient Function
Euler's totient function φ(n) for a positive integer \( n > 0 \) counts how many integers between \( 1 \) and \( n \) are coprime to \( n \).
Euler's function \( \phi(n) \) is also known as the "Euler indicator" or "Euler's totient function".
Simply put, φ(n) tells us how many numbers are coprime to \( n \), but only those that are less than \( n \).
It doesn't specify which numbers are coprime to \( n \); it only tells us "how many" there are.
What are coprime numbers? Two numbers are coprime (or relatively prime) if they have no common prime factors—in other words, their greatest common divisor (gcd) with \( n \) is 1. For instance, 10 and 9 are coprime because their factorizations, \( 10 = 5 \cdot 2 \) and \( 9 = 3^2 \), share no common prime factors.
A Practical Example
For \( n = 20 \), Euler’s function gives:
$$ \phi(20) = 8 $$
Why?
The numbers less than \( n \) that are coprime to \( n \) are:
$$ 1, 3, 7, 9, 11, 13, 17, 19 $$
Note. The gcd between \( n \) and each of these numbers is always 1. Because of this property, they are called coprime (or relatively prime) to \( n \).
Since there are 8 such numbers, we have \( \phi(20) = 8 \).
How to Compute Euler's Function
The value of \( \phi(n) \) depends on the prime factorization of \( n \).
Here's the process:
- Factorize \( n \) into its prime factors
Express \( n \) as the product of distinct prime powers: $$ n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k} $$ where \( p_1, p_2, \dots, p_k \) are distinct prime numbers, and \( e_1, e_2, \dots, e_k \) are their respective powers. - Apply Euler’s formula
The general formula for computing \( \phi(n) \) is: $$ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_k}\right) $$ where \( p_1, p_2, \dots, p_k \) are the prime factors of \( n \).
Note. If \( n \) is the product of two distinct prime numbers \( p \) and \( q \), the formula simplifies to: $$ \varphi(n) = (p - 1) \cdot (q - 1) $$ The result remains the same.
Example
Let's calculate Euler’s function for \( \phi(12) \).
First, find the prime factorization of \( n = 12 \):
$$ 12 = 2^2 \cdot 3 $$
Now, apply the formula:
$$ \phi(12) = 12 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) $$
$$ \phi(12) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} $$
$$ \phi(12) = 12 \cdot \frac{1}{3} $$
$$ \phi(12) = 4 $$
So, \( \phi(12) = 4 \). In other words, there are 4 numbers between 1 and 12 that are coprime to \( 12 \).
Verification. The numbers coprime to 12 in this range are: $$ 1, 5, 7, 11 $$ There are indeed 4 such numbers.
In this case, we cannot use the simplified formula \( \varphi(n) = (p - 1) \cdot (q - 1) \) because \( 12 \) is the product of three primes, with one repeated: \( 12 = 2 \cdot 2 \cdot 3 \).
Example 2
Let's compute \( \phi(22) \).
The prime factorization of \( n = 22 \) is \( p = 2 \) and \( q = 11 \).
Since these are two distinct prime numbers, we can use the simplified Euler’s formula:
$$ \varphi(n) = (p - 1) \cdot (q - 1) $$
$$ \varphi(22) = (2 - 1) \cdot (11 - 1) $$
$$ \varphi(22) = 1 \cdot 10 $$
$$ \varphi(22) = 10 $$
So, there are 10 numbers between 1 and 22 that are relatively prime to \( 22 \).
Verification. The numbers coprime to 22 in this range are: $$ 1, 3, 5, 7, 9, 13, 15, 17, 19, 21 $$ There are exactly 10 such numbers.
Properties of Euler’s Totient Function
One of the most fundamental properties of Euler’s function is its multiplicative property, which allows us to simplify calculations by breaking numbers down into relatively prime factors.
If two numbers \( k \) and \( j \) are relatively prime, meaning $$ \gcd(k, j) = 1 $$ then Euler’s function satisfies the property: $$ \phi(k \cdot j) = \phi(k) \cdot \phi(j) $$
If \( n \) has more than two prime factors, they must be pairwise relatively prime for this property to hold.
Example
Let's reconsider the calculation of Euler’s function for \( n = 20 \):
$$ \phi(20) = 8 $$
The number \( 20 \) can be factorized as \( 2^2 \cdot 5 \), so we apply the multiplicative property:
$$ \phi(20) = \phi(2^2 \cdot 5) = \phi(2^2) \cdot \phi(5) = \phi(4) \cdot \phi(5) = 2 \cdot 4 = 8 $$
The result is the same.
Note. We get \( \phi(4) = 2 \) because the numbers less than 4 that are relatively prime to 4 are {1,3}, which makes two. Similarly, \( \phi(5) = 4 \) because the numbers less than 5 that are relatively prime to 5 are {1,2,3,4}, which makes four.
This property also enables a useful formula for computing Euler’s function efficiently.
If \( p \) is a prime number, Euler’s function satisfies: $$ \phi(p^x) = p^x - p^{x-1} $$
This formula makes it easier to compute Euler’s function by using prime powers.
Example
Factorizing \( n = 20 \):
$$ \phi(20) = \phi(2^2 \cdot 5) = \phi(2^2) \cdot \phi(5) $$
Since 2 and 5 are prime numbers, we can apply the formula:
$$ \phi(2^2) = 2^2 - 2 = 4 - 2 = 2 $$
$$ \phi(5) = 5^1 - 5^0 = 5 - 1 = 4 $$
Thus:
$$ \phi(2^2) \cdot \phi(5) = 2 \cdot 4 = 8 $$
Note. This method is much faster, especially for large prime numbers. Listing all coprime numbers manually becomes impractical, whereas working with prime powers significantly simplifies the process.
Euler’s Theorem
Euler’s function extends Fermat’s Little Theorem to non-prime moduli.
Note. Fermat’s Little Theorem states that if \( p \) is a prime and \( a \) is an integer not divisible by \( p \), then: $$ a^{p-1} \equiv 1 \mod p $$ While powerful, this theorem only applies to prime moduli, which is a limitation.
By replacing \( p-1 \) with Euler’s function \( \phi(n) \), we obtain Euler’s Theorem:
For any two relatively prime integers \( a \) and \( n \), the following holds: $$ a^{\phi(n)} \equiv 1 \mod n $$
This generalization works for any positive integer \( n \), not just primes.
Example
Consider \( n = 20 \), which is not prime.
Let’s apply the theorem to \( a = 3 \), which is coprime to 20:
$$ 3^{\phi(20)} \equiv 1 \mod 20 $$
From earlier, we know that \( \phi(20) = 8 \), so:
$$ 3^8 \equiv 1 \mod 20 $$
Computing \( 3^8 \):
$$ 6561 \equiv 1 \mod 20 $$
Since 6561 divided by 20 leaves a remainder of 1, Euler’s theorem is verified.
Note. The division \( 6561 \div 20 \) leaves a remainder of 1, confirming the result.
Additional Notes
Some key observations about Euler’s totient function:
- How can we find the numbers coprime to \( n \)?
Euler’s function \( \phi(n) \) tells us "how many" numbers are coprime to \( n \), but not "which" numbers they are. To determine them, we check the greatest common divisor (gcd) between \( n \) and each integer from \( 1 \) to \( n-1 \). If \( \gcd(n, k) = 1 \), then \( k \) is coprime to \( n \).
Example: Let’s find the numbers coprime to \( n = 10 \). The integers from 1 to 9 are: \( 1, 2, 3, 4, 5, 6, 7, 8, 9 \). We check their gcd with 10:
- \( \gcd(1, 10) = 1 \) → 1 is coprime with 10.
- \( \gcd(2, 10) = 2 \) → 2 is not coprime with 10.
- \( \gcd(3, 10) = 1 \) → 3 is coprime with 10.
- \( \gcd(4, 10) = 2 \) → 4 is not coprime with 10.
- \( \gcd(5, 10) = 5 \) → 5 is not coprime with 10.
- \( \gcd(6, 10) = 2 \) → 6 is not coprime with 10.
- \( \gcd(7, 10) = 1 \) → 7 is coprime with 10.
- \( \gcd(8, 10) = 2 \) → 8 is not coprime with 10.
- \( \gcd(9, 10) = 1 \) → 9 is coprime with 10.
So, the numbers coprime to \( 10 \) are: \( 1, 3, 7, 9 \).
And so on.
