Computing the Euler totient function, part 3: proving phi is multiplicative

We are trying to show that the Euler totient function $\varphi(n)$ , which counts how many numbers from $1$ to $n$ share no common factors with $n$ , is multiplicative, that is, $\varphi(mn) = \varphi(m) \varphi(n)$ whenever $m$ and $n$ share no common factors. In my previous post, we looked at some illustrations, for example:

The dark blue squares are those counted by $\varphi(mn)$ , and the light blue rows and columns are those counted by $\varphi(m)$ and $\varphi(n)$ . We noted what these pictures are telling us: because we know from the Chinese Remainder Theorem that the numbers $x$ from $0$ to $mn-1$ correspond exactly to pairs of numbers $(x \bmod m, x \bmod n)$ , showing that $\varphi$ is multiplicative really comes down to showing the following fact:

$x$ is relatively prime to $mn$ if and only if $x\bmod m$ is relatively prime to $m$ and $x \bmod n$ is relatively prime to $n$ .

In other words, the dark blue cells show up precisely at the intersections of light blue rows and columns. Let’s prove this!

First, if $x$ shares no common factors with the product $mn$ , then it can’t possibly share any common factors with $m$ or $n$ individually. This is because any divisor of $m$ is also a divisor of $mn$ , and likewise for $n$ ; so if $x$ did share any common factor with, say, $m$ , then it would automatically be a common factor with $mn$ . The converse is also true: if $x$ shares no common factors with $m$ and also shares no common factors with $n$ , then it can’t share any common factors with $mn$ . That is,

(A) $x$ is relatively prime to $mn$ if and only if $x$ is relatively prime to $m$ and $xn$ is relatively prime to $n$ .

For the second piece of the puzzle, note that by definition, $x \bmod m = x - qm$ for some integer $q$ . That is, $x \bmod m$ is what is left over after we subtract some number of copies of $m$ from $x$ . If $x$ shares a common factor $d$ with $m$ , then so does $x \bmod m = x - qm$ , since we could factor $d$ out of both $x$ and $qm$ . Likewise, if we add $qm$ to both sides to get $x = qm + x \bmod m$ , we can see that if $x \bmod m$ shares a common factor $d$ with $m$ , then so does $x$ —since once again we could factor $d$ out of both $qm$ and $x \bmod m$ . Thus we have shown that

$x$ shares a common factor with $m$ if and only if $x \bmod m$ shares a common factor with $m$ ,

or, taking the contrapositive of this statement,

(B) $x$ is relatively prime to $m$ if and only if $x \bmod m$ is relatively prime to $m$ .

Now let’s put the puzzle pieces together:

$\begin{array}{c}x \text{ is relatively prime to } mn \\[1.2em] \text{if and only if (by (A))} \\[1.2em] x \text{ is relatively prime to } m \text{ \textbf{and} } x \text{ is relatively prime to } n \\[1.2em] \text{if and only if (by (B), twice)} \\[1.2em] x \bmod m \text{ is relatively prime to } m \text{ \textbf{and} } x \bmod n \text{ is relatively prime to } n \end{array}$

which is exactly what we set out to prove.

The Chinese Remainder Theorem tells us that when $m$ and $n$ are relatively prime, there is a 1-1 matchup between the numbers $0 \leq x < mn$ and the pairs of numbers $(a,b)$ such that $0 \leq a < m$ and $0 \leq b < n$ . But we now know we can make an even finer distinction: $0 \leq x < mn$ which are relatively prime to $mn$ are in 1-1 correspondence with pairs $(a,b)$ where $a$ is relatively prime to $m$ and $b$ is relatively prime to $n$ . Hence, $\varphi(mn) = \varphi(m)\varphi(n)$ .