Proofs for totient function and euler's theorem

This post is to provide some proofs for the formulae discussed in Nishchay’s lecture on 29/09/2020

The first theorem is about Euler’s totient function \phi(n) which is the number of positive integers less than n and co-prime to n

  1. Euler’s totient function \phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k}) where p_1, p_2, ... p_k are prime divisors of n

A. \phi(p^k) = p^k - p^{k-1} \ \ \forall \ \ primes \ \ p

\it{proof.} gcd(x, p^k) = 1 if and only if x is not divisible by p
Numbers less than p^k and divisible by p are p, 2p, 3p, .... (p^{k-1}) p, which implies \phi(p^k) = p^k - p^{k-1}

B. \phi(ab) = \phi(a) \phi(b) if gcd(a,b) = 1

\it{proof.} Consider the numbers 1 to ab as written row-wise in an a x b grid as follows

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3 \ ... \ \ \ a
\ \ \ \ \ \ \ \ \ \ \ \ a+1 \ \ \ \ \ \ \ \ \ \ \ \ \ a+2 \ \ \ \ \ \ \ \ \ \ \ \ \ a+3 \ ... \ 2a
\ \ \ \ \ \ \ \ \ \ 2a+1 \ \ \ \ \ \ \ \ \ \ \ 2a+2 \ \ \ \ \ \ \ \ \ \ \ 2a+3 \ ... \ 3a
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ .
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ .
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ .
(b-1)a+1 \ (b-1)a+2 \ (b-1)a+3 \ ... \ ba

The number at row x and column y is ax + y
Since a and b are co-prime, gcd(ab, x) = 1 is equivalent to gcd(a, x) = 1 and gcd(b, x) = 1
From Euclid’s gcd algorithm, we know that gcd(a, ax+y) = gcd(a, y)

Therefore consider column numbers y, with gcd(y, a) = 1 then all numbers in those columns are co-prime to a. So for \phi(a) columns, all numbers in those columns are co-prime to a.

Now for b, gcd(b, ax+y) = gcd(b, (ax+y)\mod b)
Let’s look at a fixed column (y) and find out the values of (ax + y) \mod b for x = 0, 1, ... b-1

There are clearly b values (1 for each value of x).

Suppose two of them (x_1 and x_2) are equal, then we would have ax_1 + y \equiv ax_2 + y \mod b \implies a(x_1 - x_2) \equiv 0 \mod b
Since gcd(a, b) = 1, (x_1 - x_2) must be divisible by b.
But -b+1 \leq x_1-x_2 \leq b-1, this forces x_1 = x_2, a contradiction.
Therefore all of them must be \bold{different}

So if we consider the values of (ax+y) \mod b we will obtain 0, 1, 2, ..., b-1 in some order. Therefore for every column, there are exactly \phi(b) rows for which every element in that row is co-prime with b.

So total number of choices we have for numbers co-prime with a and b is \phi(a)\phi(b). This gives the required answer.

  1. a^{\phi(m)} \equiv 1 \mod m if gcd(a, m) = 1

\it{proof}. Consider the numbers x_1, x_2, ... x_{\phi(m)} which are co-prime to m and less than to m.

Consider the numbers ax_1, ax_2, ... ax_{\phi(m)}
If two of them are equal modulo m then ax_i \equiv ax_j \mod m \implies a(x_i - x_j) \equiv 0 \mod m
Since gcd(a, m) is 1, (x_i - x_j) is divisible by m.
But 0 \leq x_i \leq m-1 so -(m-1) \leq x_i - x_j \leq (m-1)
So only way (x_i - x_j) is divisible by m, is if x_i - x_j = 0 or x_i = x_j. This means all ax_i's are different \mod m.

So ax_1, ax_2, ... ax_{\phi(m)} are all different \mod m and co-prime with m (remember both a and x_i's are co-prime with m.

This means ax_1, ax_2, .... ax_{\phi(m)} are same as x_1, x_2, ... x_{\phi(m)} (but maybe in a different order).

Since they are the same set of numbers (maybe in different order), their product must be same.

ax_1 . ax_2 .... ax_{\phi(m)} \equiv x_1 . x_2 . ... x_{\phi(m)} \mod m
\implies a^{\phi(m)} x_1 . x_2 . ... x_{\phi(m)} \equiv x_1 . x_2 . ... x_{\phi(m)} \mod m
\implies (a^{\phi(m)} - 1) (x_1 . x_2 . ... x_{\phi(m)}) \equiv 0 \mod m

All the x_i's are co-prime to m, so none of them can be divisible by m, so the left over term must be divisible by m, which gives the required theorem.

  1. a^b \equiv a ^ c \mod m if gcd(a, m) = 1 and b \equiv c \mod \phi(m)

\it{proof}. Let b \mod \phi(m) be b_r, then b = b_r + q\phi(m) for some integer q.

Then a ^ b = a^{b_r + y\phi(m)} = a^{b_r} . (a^{\phi(m)})^y
If we consider \mod m, we know that the second term is equivalent to 1 by theorem above.

3 Likes