Integers II. Euler's totient.

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.

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.

Properties

• If p is a prime, φ(p) = p-1

• φ(p^k) = p^k -p^k-1 = p^k-1(p -1), e.g., φ(8) = φ(2³) = 2³ -2² = 8 -4 = 4. φ(9) = φ(3²) = 3² -3¹ = 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₁^α₁p₂^α₂···p_n^α_n, φ(n) = [φ(ab) = φ(a)φ(b)] φ(p₁^α₁)φ(p₂^α₂)···φ(p_n^α_n) = [φ(p^k) = p^k-1(p -1)] = p₁^α₁-1(p₁ -1)p₂^α₂-1(p₂ -1)···p_n^α_n-1(p_n -1), e.g., φ(12) = φ(2²·3) = 2(2-1)3⁰(3-1) = 4, φ(20) = φ(2²·5) = 2(2-1)5⁰(5-1) = 2·4 = 8, φ(75) = φ(5²·3) = 5(5-1)3⁰(3-1) = 5·4·2 = 40.

• Euler’s product formula: If n = p₁^α₁p₂^α₂···p_n^α_n, φ(n) = [φ(ab) = φ(a)φ(b)] φ(p₁^α₁)φ(p₂^α₂)···φ(p_n^α_n) = [φ(p^k) = p^k(1 -1/p)] = p₁^α₁(1 -1/p₁)p₂^α₂(1 -1/p₂)···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).

Applications

• 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.

The Method of Repeated Squares

What is 5⁷ mod 21 or 271³²¹ (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^k₁ + 2^k₂ + … + 2^k_n, e.g., 7₁₀ = 111₂ and 321₁₀= 101000001₂.

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²⁰ (mod n), a²¹ (mod n), …, a^2k (mod n)

5⁷ mod 21 ≡ 5⁴⁺²⁺¹ mod 21

1. 5¹ = 5 mod 21 = 5
2. 5² = 25 ≡ 4 mod 21
3. 5⁴ = (5²)² ≡ [It’s time to use the previous one] 4² ≡ 16 mod 21.

Finally, let’s combine our partial results, 5⁷ mod 21 ≡ 5⁴⁺²⁺¹ 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²⁰· 271²⁶· 271²⁸ (mod 481)

1. 271²⁰ ≡ 271 (mod 481)
2. 271²¹ ≡ 73441 (mod 481) ≡ 329 (mod 481)
3. 271²² ≡ [Using the previous result] 329² ≡ 108241 ≡ 16 (mod 481).
4. 271²³ ≡ 16² ≡ 256 (mod 481).
5. 271²⁴ ≡ 256² ≡ 120 (mod 481).
6. 271²⁵ ≡ 120² ≡ 451 (mod 481).
7. 271²⁶ ≡ 451² ≡ 419 (mod 481).
8. 271²⁷ ≡ 419² ≡ 477 (mod 481).
9. 271²⁸ ≡ 477² ≡ 16 (mod 481).

Finally, let’s combine our partial results, 271^20+26+28 ≡ 271²⁰· 271²⁶· 271²⁸ (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).