The Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. In other words, φ(1) = 1, and for any n ∈ ℤ, n > 1, φ(n) is the number of positive integers a less than n (a ≤ n) and relative prime to n, (a, n) = 1, e.g., φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6, φ(8) = 4.
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
The Euler φ-function is a map φ:ℤ^{+} → ℝ such that φ(1) = 1 and φ(n) is equal to the number of positive integers coprime to n for n > 1.
If p is a prime, φ(p) = p-1
φ(p^{k}) = p^{k} -p^{k-1} = p^{k-1}(p -1), e.g., φ(8) = φ(2^{3}) = 2^{3} -2^{2} = 8 -4 = 4. φ(9) = φ(3^{2}) = 3^{2} -3^{1} = 9 -3 = 6.
φ is multiplicative, that is, if two numbers are coprime gcd(a, b) = 1 ⇒ φ(ab) = φ(a)φ(b), e.g., φ(6) = φ(2)φ(3) = 1·2 = 2, φ(12) = φ(4)·φ(3) = 2·2 = 4, φ(40) = φ(8)φ(5) = 4·4 = 16.
If n = p_{1}^{α1}p_{2}^{α2}···p_{n}^{αn}, φ(n) = [φ(ab) = φ(a)φ(b)] φ(p_{1}^{α1})φ(p_{2}^{α2})···φ(p_{n}^{αn}) = [φ(p^{k}) = p^{k-1}(p -1)] = p_{1}^{α1-1}(p_{1} -1)p_{2}^{α2-1}(p_{2} -1)···p_{n}^{αn-1}(p_{n} -1), e.g., φ(12) = φ(2^{2}·3) = 2(2-1)3^{0}(3-1) = 4, φ(20) = φ(2^{2}·5) = 2(2-1)5^{0}(5-1) = 2·4 = 8, φ(75) = φ(5^{2}·3) = 5(5-1)3^{0}(3-1) = 5·4·2 = 40.
Euler’s product formula: If n = p_{1}^{α1}p_{2}^{α2}···p_{n}^{αn}, φ(n) = [φ(ab) = φ(a)φ(b)] φ(p_{1}^{α1})φ(p_{2}^{α2})···φ(p_{n}^{αn}) = [φ(p^{k}) = p^{k}(1 -1/p)] = p_{1}^{α1}(1 -1/p_{1})p_{2}^{α2}(1 -1/p_{2})···p_{n}^{αn}(1 -1/p_{n}) = n$\prod_{p|n} (1-\frac{1}{p})$
Euler’s theorem. Let a, n ∈ ℤ, n > 0 and gcd(a, n) = 1. Then, a^{φ(n)}≡1 (mod n).
For each n > 1, we define U_{n} to be the set of all positive integers less than n that have a multiplicative inverse modulo n, that is, there is an element b∈ Z_{n} such that ab = 1. U_{n} = {a ∈ Z_{n}: a is relatively prime to n, a < n} = {a ∈ Z_{n}: gcd(k, n)=1}. In particular, |U_{n}| = φ(n)
Cyclic groups. If d is a positive divisor of n, the number of elements of order d in a cyclic group of order n is φ(d).
Cyclic groups. Let |a|=n. Then ⟨a⟩=⟨a^{j}⟩ iff $\frac{n}{gcd(n, j)}=n$ ↭ gcd(n, j) = 1. In particular, the number of generators of ⟨a⟩ is φ(n) where φ is Euler’s φ-function.
What is 5^{7} mod 21 or 271^{321} (mod 481)?
The first step is to write the exponent in binary. Of course, every number a can be written as the sum of distinct power of 2, a = 2^{k1} + 2^{k2} + … + 2^{kn}, e.g., 7_{10} = 111_{2} and 321_{10}= 101000001_{2}.
The laws of exponents still work in ℤ_{n} [b≡a^{x} (mod n), c≡a^{y} (mod n) ⇒ bc≡a^{x+y} (mod n),] so we can calculate a^{2k} (mod n) in k multiplications by computing a^{20} (mod n), a^{21} (mod n), …, a^{2k} (mod n)
5^{7} mod 21 ≡ 5^{4+2+1} mod 21
Finally, let’s combine our partial results, 5^{7} mod 21 ≡ 5^{4+2+1} mod 21 ≡ 16·4·5 mod 21 ≡ 320 mod 21 ≡ 5 mod 21.
Analogously, but we will need a little more extra effort, 271^{20+26+28} ≡ 271^{20}· 271^{26}· 271^{28} (mod 481)
Finally, let’s combine our partial results, 271^{20+26+28} ≡ 271^{20}· 271^{26}· 271^{28} (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).