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

- If
`p`

is prime then`φ(p) = p-1`

- If
`p`

and`q`

are comprime then`φ(p·q) = φ(p)·φ(q)`

- 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