## 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)$. 