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

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.

# Properties

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

# Applications

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

# The Method of Repeated Squares

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

1. 51 = 5 mod 21 = 5
2. 52 = 25 ≡ 4 mod 21
3. 54 = (52)2 ≡ [It’s time to use the previous one] 42 ≡ 16 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)

1. 27120 ≡ 271 (mod 481)
2. 27121 ≡ 73441 (mod 481) ≡ 329 (mod 481)
3. 27122 ≡ [Using the previous result] 3292 ≡ 108241 ≡ 16 (mod 481).
4. 27123 ≡ 162 ≡ 256 (mod 481).
5. 27124 ≡ 2562 ≡ 120 (mod 481).
6. 27125 ≡ 1202 ≡ 451 (mod 481).
7. 27126 ≡ 4512 ≡ 419 (mod 481).
8. 27127 ≡ 4192 ≡ 477 (mod 481).
9. 27128 ≡ 4772 ≡ 16 (mod 481).

Finally, let’s combine our partial results, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).

Bitcoin donation