 # Euler's Totient

Created: 2017-08-19
Updated: 2017-08-19

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 