D   A   T   A   W   O   K





Creation: August 19 2017
Modified: September 11 2018

Euler's Totient Function


Given a natural number n, the Euler φ function, aka Euler Totient, applied to n represents the number of positive numbers less than n that are coprime to n.

Euler's Product formula

φ(n) = n ⋅ ∏ (1 - 1/p), p|n

( ∏ : n-ary product )

The product is over the distinct prime numbers dividing n.

The proof of Euler's product formula depends on two important facts:

Proof.

The fundamental theorem of arithmetic states that if n>1 there is a unique expression for n = p1^k1 ⋅ p2^k2 ⋅ ... ⋅ pr^kr, where p1 < p2 < ... < pn are prime numbers and each ki > 0.

Repeatedly using the multiplicative property of φ and the formula for φ(p^k) gives

φ(n) = φ(p1^k1 ⋅ ... ⋅ pr^kr)
= φ(p1^k1) ⋅ ... ⋅ φ(pr^kr)
= p1^k1⋅(1-1/p1) ⋅ ... ⋅ pr^kr⋅(1-1/pr)
= p1^k1 ⋅ ... ⋅ pr^kr ⋅ (1-1/p1) ⋅ ... ⋅ (1-1/pr)
= n ⋅ ∏ (1 - 1/p), p|n*


Multiplicative Property

If gcd(m, n) = 1, the Euler Totient is a multiplicative function

φ(mn) = φ(m)φ(n)

Proof.

Make a matrix of the numbers 1 to mn with m rows and n columns.

1 m + 1 2m + 1 ... (n-1)m + 1
2 m + 2 2m + 2 ... (n-1)m + 2
3 m + 3 2m + 3 ... (n-1)m + 3
. ... ... ... ...
m m + m 2m + m ... (n-1)m + m

In general the number in the i-th row and j-th column is: (j-1)m + i.

The numbers in the r-th row are of the form km + r as k runs from 0 to n-1.

Let d = gcd(r,m).

If d > 1 then no number in the r-th row of the table is relatively prime to mn, since d|(km+r) for all k. ( d|m and d|(km+r) then gcd(mn,km+r) is at least d>1 )

So to count the residues relatively prime to mn we need to look at the rows indexed by values of r such that gcd(r,m) = 1, and there are φ(m) such rows (by definition of φ).

If d = 1 then every entry in the r-th row is relatively prime to m, since gcd(km+r,m) = 1 by the Euclidean algorithm.

Because {0,...,(n-1)} is a complete set of representatives modulo n, then follows from the lemmas below(*) that the entries in the r-th row form a complete set of representatives modulo n (Lemma 1 and Lemma 2). Thus exactly φ(n) of them will be relatively prime to n, and thus relatively prime to mn (Lemma 3).

(*) Lemma 1

If {a1,...,an} is a complete set of representatives, then for any integer b, {a1+b,...,an+b} is a complete set of representatives.

Proof.

If not, then ai+b ≡ aj+b (mod n) and then ai ≡ aj (mod n), contradicting the hypothesis.

(*) Lemma 2

If {a1,...,an} is a complete set of representatives, then {b*a1,...,b*an} is a complete set of representatives iff gcd(b,n)=1.

Proof.

If gcd(b,n)=1 and ai⋅b ≡ aj⋅b (mod n) then there exists the inverse of b (mod n). Thus follows that ai ≡ aj, contradicting the hyp.

Conversely, if gcd(b,n)=d with 1 < d < n, then b is a zero-divisor, that is there exists a value z with 1 < z < n such that b⋅z ≡ 0 (mod n). Thus, int this case the set {ba1,...,ban} cannot be a complete set of representatives because there are two elements congruent to 0 modulo n.

(*) Lemma 3

If a is relatively prime to m and a is relatively prime to n, then a is relatively prime to mn.

Proof

Using the Bezout identity: as + mt = 1, ah + nk = 1

Multiplying the two equations we get: a(ash + snk + mht) + mntk = 1

Follows that gcd(a, mn) = 1


Value for a prime power argument

Given a prime number p, and a natural number n:

φ(p^n) = p^n - p^(n-1) = p^(n-1)⋅(p-1) = p^n⋅(1-1/p)

Proof.

Create a list of the numbers from 1 to p^n and count how many numbers in the list are not relatively prime to p^n. Because p is prime we indeed are counting the multiples of p that are less than p^n. There are p^(n-1) such multiples, they are: p, 2p, 3p, ..., p^(n-1)p. Thus among the p^n numbers, there are p^n - p^(n-1) that are relatively prime to p^n.


Some values of the function

n a(n)
1 1
2 1
3 2
4 2
5 4
6 2
7 6
8 4
9 6
10 4
11 10
12 4
13 12
14 6
15 8
16 8
17 16
18 6
19 18
20 8
21 12
22 10
23 22
24 8
25 20
26 12
27 18
28 12
29 28
30 8
31 30
32 16
33 20
34 16
35 24
36 12
37 36
38 18
39 24
40 16
41 40
42 12
43 42
44 20
45 24
46 22
47 46
48 16
49 42
50 20
51 32
52 24
53 52
54 18
55 40
56 24
57 36
58 28
59 58
60 16
61 60
62 30
63 36
64 32
65 48
66 20
67 66
68 32
69 44
int v[] = {1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,
           10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,
           24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,
           40,24,36,28,58,16,60,30,36,32,48,20,66,32,44};

References

davxy