Euler's Totient Function

Euler's Totient Function

Before presenting Euler's theorem, we need to introduce an important quantity in number theory, referred to as Euler's totient function and written f(n), defined as the number of positive integers less than n and relatively prime to n. By convention, f(1) = 1.

Determine f(37) and f(35). Because 37 is prime, all of the positive integers from 1 through 36 are relatively prime to 37. Thus f(37) = 36. To determine f(35), we list all of the positive integers less than 35 that are relatively prime to it: 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34. There are 24 numbers on the list, so f(35) = 24.

Table 8.2 lists the first 30 values of f(n). The value f(1) is without meaning but is defined to have the value 1.

Table 8.2. Some Values of Euler's Totient Function f(n)

n	f(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

It should be clear that for a prime number p,

f(p) = p 1

Now suppose that we have two prime numbers p and q, with p q. Then we can show that for n = pq,

f(n) = f(pq) = f(p) x f(q) = (p 1) x (q x 1)

To see that f(n) = f(p) x f(q), consider that the set of positive integers less that n is the set {1,..., (pq 1)}. The integers in this set that are not relatively prime to n are the set {p,2 p,..., (q 1)p} and the set {q,2q,..., (p 1)q} Accordingly,

f(n) = (pq 1) [(q 1) + (p 1)]

= pq (p + q) + 1

= (p 1) x (q 1)

= f(p) x f(q)

f(21) = f(3) x f(7) = (3 1) x (7 1) = 2 x 6 = 12
where the 12 integers are {1,2,4,5,8,10,11,13,16,17,19,20}

Euler's Theorem

Euler's theorem states that for every a and n that are relatively prime:

a = 3; n = 10; f(10) = 4	af(n) = 34 = 81 1(mod 10) = 1 (mod n)
a = 2; n = 11; f(11) = 10	af(n) = 210 = 1024 1(mod 11) = 1 (mod n)

Proof: Equation (8.4) is true if n is prime, because in that case f(n) = (n 1) and Fermat's theorem holds. However, it also holds for any integer n. Recall that f(n) is the number of positive integers less than n that are relatively prime to n. Consider the set of such integers, labeled as follows:

R {x₁, x₂,..., x_f(n)}

That is, each element x_i of R is a unique positive integer less than n with gcd(x_i, n) = 1. Now multiply each element by a, modulo n:

S = {(ax₁ mod n), (ax₂ mod n),..., (ax_f(n) mod n)}

The set S is a permutation of R, by the following line of reasoning:

1. Because a is relatively prime to n and x_i is relatively prime to n, ax_i must also be relatively prime to n. Thus, all the members of S are integers that are less than n and that are relatively prime to n.
2. There are no duplicates in S. Refer to Equation (4.3). If ax_i mod n = ax_j mod n then x_i = x_j.

Therefore,

This is the same line of reasoning applied to the proof of Fermat's theorem. As is the case for Fermat's theorem, an alternative form of the theorem is also useful:

Again, similar to the case with Fermat's theorem, the first form of Euler's theorem [Equation (8.4)] requires that a be relatively prime to n, but this form does not.