D   A   T   A   W   O   K

• home
• projects
• keyring
• NOTES
• feed
• propaganda

Euler's Totient Function

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.

Euler's Product formula

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

Multiplicative Property

φ(mn) = φ(m)φ(n)

Proof.

Make a matrix of the numbers 1 to mn with m rows and n columns.

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 {ba1,...,ban} 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

Value for a prime power argument

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.

Some values of the function

References

• Sequence A000010 in the OEIS
• Wikipedia

Proudly self-hosted on a cheap Raspberry Pi