Given a natural number n, the Euler φ function, also known as Euler’s Totient, applied to n represents the number of positive numbers less than n that are coprime to n.

Euler’s Totient function

φ(n) = n · ∏ (1 - 1/pi)

With pi a prime in the factorization of n.

The proof of Euler’s product formula relies on two important properties:

1. If p is prime then φ(p) = p-1
2. If p and q are comprime then φ(p·q) = φ(p)·φ(q)
3. If p is prime then φ(p^n) = p^n·(1-1/p)

Proof

From the above propositions and the unique factorization of any integer we have the general formula:

φ(n) = φ(∏ pi^ei) = ∏ φ(pi^ei) = ∏ pi^ei·(1 - 1/pi) = n·∏(1 - 1/pi)

Value for two primes product

For two primes p and q

φ(p·q) = φ(p)·φ(q)

Proof

Given two primes p and q, the elements x < p·q such that (x, p·q) ≠ 1 are:

• A = { 0 }
• B = { p, 2·p, 3·p, ..., (q-1)·p }
• C = { q, 2·q, 3·q, ..., (p-1)·q }

The 3 sets are disjointed.

That is, if p·i = q·j → q|p·i → q|i (because p is prime) and this is impossible because i < q.

Follows that:

φ(p·q) = |Z_(p·q)| - (|A| + |B| + |C|)
       = p·q - (1 + p-1 + q-1) = p·q - p - q + 1
       = (p-1)·(q-1) = φ(p)·φ(q)

∎

Note that the proof doesn’t include the case where a and b are not both primes but are coprimes.

The missing piece can be proven via the Chinese Reminder Theorem.

Value for two coprimes product

See Chinese Reminder Theorem applications.

Value for a prime power

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

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

Proof

Create a list of the numbers less than p^n and count how many numbers in the list are not relatively prime to p^n.

Because p is prime we are counting the multiples of p that are less than p^n. There are p^(n-1) such multiples, they are:

{ 0, p, 2·p, 3·p, ..., p^(n-2)·p }

Thus, among the p^n numbers, p^n - p^(n-1) = p^n·(1 - 1/p) are relatively prime to p^n.

∎

Some values of the function

As can be easily seen from the table and the graph, the function is not monotonic.

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

References

• Sequence A000010 in the OEIS
• Wikipedia
• Chinese Reminder Theorem