Creation: August 19 2017

Modified: January 22 2020

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.

*φ(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:

- The function is multiplicative:
*φ(mn) = φ(m)φ(n)* - Value for a prime power argument:
*φ(p^n) = p^n⋅(1-1/p)*

*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*

*φ(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 *{b*a1,...,b*an}* 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*

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*.

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};
```