The Euler's totient function, or phi (φ) function is a very important number theoretic function having a deep relationship to prime numbers and the so-called order of integers. The totient φ(n) of a positive integer n greater than 1 is defined to be the number of positive integers less than n that are coprime to n. φ(1) is defined to be 1. The following table shows the function values for the first several natural numbers:
| n | φ(n) | numbers coprime to n |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 1, 2 |
| 4 | 2 | 1,3 |
| 5 | 4 | 1,2,3,4 |
| 6 | 2 | 1,5 |
| 7 | 6 | 1,2,3,4,5,6 |
| 8 | 4 | 1,3,5,7 |
| 9 | 6 | 1,2,4,5,7,8 |
| 10 | 4 | 1,3,7,9 |
| 11 | 10 | 1,2,3,4,5,6,7,8,9,10 |
| 12 | 4 | 1,5,7,11 |
| 13 | 12 | 1,2,3,4,5,6,7,8,9,10,11,12 |
| 14 | 6 | 1,3,5,9,11,13 |
| 15 | 8 | 1,2,4,7,8,11,13,14 |
Can you find some relationships between n and φ(n)? One thing you may have noticed is that:
when n is a prime number (e.g. 2, 3, 5, 7, 11, 13), φ(n) = n-1.
But how about the composite numbers? You may also have noticed that, for example, 15 = 3*5 and φ(15) = φ(3)*φ(5) = 2*4 = 8. This is also true for 14,12,10 and 6. However, it does not hold for 4, 8, 9. For example, 9 = 3*3 , but φ(9) = 6 ≠ φ(3)*φ(3) = 2*2 =4. In fact, this multiplicative relationship is conditional:
when m and n are coprime, φ(m*n) = φ(m)*φ(n).
The general formula to compute φ(n) is the following:
If the prime factorisation of n is given by n =p1e1*...*pnen, then φ(n) = n *(1 - 1/p1)* ... (1 - 1/pn).
For example:
9 = 32, φ(9) = 9* (1-1/3) = 6
4 =22, φ(4) = 4* (1-1/2) = 2
15 = 3*5, φ(15) = 15* (1-1/3)*(1-1/5) = 15*(2/3)*(4/5) =8
Euler’s theorem generalises Fermat’s theorem to the case where the modulus is not prime. It says that:
if n is a positive integer and a, n are coprime, then aφ(n) ≡ 1 mod n where φ(n) is the Euler's totient function.
Let's see some examples:
165 = 15*11, φ(165) = φ(15)*φ(11) = 80. 880 ≡ 1 mod 165
1716 = 11*12*13, φ(1716) = φ(11)*φ(12)*φ(13) = 480. 7480 ≡ 1 mod 1716
φ(13) = 12, 912 ≡ 1 mod 13
We can see that Fermat's little theorem is a special case of Euler's Theorem: for any prime n, φ(n) = n-1 and any number a 0< a <n is coprime to n. From Euler's Theorem, we can easily get several useful corollaries. First:
if n is a positive integer and a, n are coprime, then aφ(n)+1 ≡ a mod n.
This is because aφ(n)+1 = aφ(n)*a, aφ(n) ≡ 1 mod n and a ≡ a mod n, so aφ(n)+1 ≡ a mod n. From here, we can go even further:
if n is a positive integer and a, n are coprime, b ≡ 1 mod φ(n), then ab ≡ a mod n.
If b ≡ 1 mod φ(n), then it can be written as b = k*φ(n)+1 for some k. Then ab = ak*φ(n)+1 = (aφ(n))k*a. Since aφ(n) ≡ 1 mod n, (aφ(n))k ≡ 1k ≡ 1 mod n. Then (aφ(n))k*a ≡ a mod n. This is why RSA works.
Useful Links