Computing the Euler totient function, part 2: seeing phi is multiplicative

In my last post, I claimed that $\varphi(mn) = \varphi(m) \varphi(n)$ whenever $m$ and $n$ are relatively prime. (Recall that $\varphi(n)$ counts how many numbers from $1$ to $n$ share no factors in common with $n$ .)

Let’s get some intuition for this by looking at some $m \times n$ Chinese remainder theorem grids and highlighting the numbers which are relatively prime to $mn$ . So, for example, the first grid below is $3 \times 5$ ; I’ve filled it in with consecutive numbers from $0$ to $14$ along the diagonal, and highlighted all the numbers that share no common factors with $15$ . (I’ve also labelled the rows and columns with smaller numbers counting from $0$ .) Below that I’ve also chosen to show similar $3 \times 8$ , $5 \times 6$ , and $8 \times 9$ grids.

And here’s a slightly bigger example ( $14 \times 15$ ):

There are some striking patterns here. The placement of the highlighted cells is clearly not random: they are precisely confined to certain rows and columns. (Incidentally, this is exactly what I was trying to show in my last post without words, though I think the colors may have been somewhat distracting.) Which rows and columns are they? Let’s have a look. Below I’ve drawn the $8 \times 9$ grid again, this time highlighting the rows and columns where cells relatively prime to $72$ occur:

Notice that the highlighted rows (1, 3, 5, 7) are exactly the numbers relatively prime to 8, and the highlighted columns (1, 2, 4, 5, 7, 8) are the ones relatively prime to 9. The number of dark blue intersection points is just the number of highlighted rows times the number of highlighted columns: there are four highlighted rows and six highlighted columns, making a total of 24 dark blue squares. That is, $\varphi(72) = \varphi(8) \varphi(9)$ .

You can check that this is true for the other examples I showed above as well. So can we turn this into a conjecture? Remember that when we label an $m \times n$ grid with consecutive numbers along the diagonal, the number $x$ ends up at the grid coordinates $(x \mod m, x \mod n)$ (see this post). We’re guessing that cells containing numbers relatively prime to $mn$ end up precisely where the row number is relatively prime to $m$ and the column number is relatively prime to $n$ , so we can translate this into the more formal statement

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

We’ll prove this next time!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →