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

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, counting and tagged , , , . Bookmark the permalink.

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

  1. Pingback: Computing the Euler totient function, part 4: totient of prime powers | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.