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
φ(pk) = pk -pk-1 = pk-1(p -1), e.g., φ(8) = φ(23) = 23 -22 = 8 -4 = 4. φ(9) = φ(32) = 32 -31 = 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 = p1α1p2α2···pnαn, φ(n) = [φ(ab) = φ(a)φ(b)] φ(p1α1)φ(p2α2)···φ(pnαn) = [φ(pk) = pk-1(p -1)] = p1α1-1(p1 -1)p2α2-1(p2 -1)···pnαn-1(pn -1), e.g., φ(12) = φ(22·3) = 2(2-1)30(3-1) = 4, φ(20) = φ(22·5) = 2(2-1)50(5-1) = 2·4 = 8, φ(75) = φ(52·3) = 5(5-1)30(3-1) = 5·4·2 = 40.
Euler’s product formula: If n = p1α1p2α2···pnαn, φ(n) = [φ(ab) = φ(a)φ(b)] φ(p1α1)φ(p2α2)···φ(pnαn) = [φ(pk) = pk(1 -1/p)] = p1α1(1 -1/p1)p2α2(1 -1/p2)···pnαn(1 -1/pn) = 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 Un 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∈ Zn such that ab = 1. Un = {a ∈ Zn: a is relatively prime to n, a < n} = {a ∈ Zn: gcd(k, n)=1}. In particular, |Un| = φ(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⟩=⟨aj⟩ 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 57 mod 21 or 271321 (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 = 2k1 + 2k2 + … + 2kn, e.g., 710 = 1112 and 32110= 1010000012.
The laws of exponents still work in ℤn [b≡ax (mod n), c≡ay (mod n) ⇒ bc≡ax+y (mod n),] so we can calculate a2k (mod n) in k multiplications by computing a20 (mod n), a21 (mod n), …, a2k (mod n)
57 mod 21 ≡ 54+2+1 mod 21
Finally, let’s combine our partial results, 57 mod 21 ≡ 54+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, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481)
Finally, let’s combine our partial results, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).