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

Posted in arithmetic, computation, counting | Tagged , , , | Leave a comment

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!

Posted in arithmetic, computation, counting | Tagged , , | 1 Comment

Computing the Euler totient function, part 1

Recall that Euler’s totient function \varphi(n) counts how many of the integers from 1 to n are relatively prime to n, that is, share no factors in common with n. For example, \varphi(12) = 4, since only 1, 5, 7, and 11 share no factors with 12; on the other hand \varphi(13) = 12, since every number from 1 to 12 shares no common factors with 13. We’ve encountered this function many times before, but I’ve never actually talked about how to compute it!

Of course, we could just count: that is, to compute \varphi(n), list all the numbers from 1 to n, and compute the GCD of each number with n (using the Euclidean algorithm); count the ones for which the GCD is 1. This works, of course, but it is possible to compute \varphi(n) much faster than this.

The key to computing \varphi more quickly is that it is has the special property of being multiplicative: if m and n are relatively prime, then \varphi(mn) = \varphi(m) \varphi(n) (don’t take my word for it though—we’ll prove it!).

Recall that we can break any number down as a product of distinct prime powers,

n = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}.

For example, 360 = 2^3 \cdot 3^2 \cdot 5^1. Of course, any powers of two different primes are relatively prime to each other (they are only divisible by their respective primes), so if \varphi is multiplicative it means we can break down \varphi(n) like this:

\varphi(n) = \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \dots \varphi(p_n^{k_n}).

Then all we have left to do is figure out how to compute \varphi(p^k) for some power of a prime p. That is, we’ve reduced a harder problem (“how many numbers are relatively prime to an arbitrary integer n?”) to a more specific and hopefully easier one (“how many numbers are relatively prime to an integer of the form p^k for some prime number p?”). Some questions we still have to answer:

  1. How do we know that \varphi(mn) = \varphi(m) \varphi(n) when m and n are relatively prime? (Hint: look at my previous post and the one before that…)

  2. How do we find \varphi(p^k)? You might like to try figuring this out too. As a warmup, what is \varphi(p)? Then what about \varphi(p^2)? Can you generalize?

Posted in arithmetic, computation, counting | Tagged , , | Leave a comment

Post without words #26

Image | Posted on by | Tagged , , | 2 Comments

Chinese Remainder Theorem proof

In my previous post I stated the Chinese Remainder Theorem, which says that if m and n are relatively prime, then the function

c(x) = (x \bmod m, x \bmod n)

is a bijection between the set [mn] and the set of pairs [m] \times [n] (remember that the notation [k] means the set \{0, \dots, k - 1\}). In other words, if we draw an m \times n grid and trace out a diagonal path, wrapping around when we get to an edge, we will hit every grid square exactly once before returning to the start. In other other words, the set of equations x \equiv a \pmod m, x \equiv b \pmod n always has a unique solution x (that is, unique \pmod {mn}) when m and n are relatively prime.

Let’s prove it! First, let’s prove that the function c is one-to-one, that is, any two different values of x are sent to different pairs (x \bmod m, x \bmod n). In other words, if x_1 and x_2 are not equal, then c(x_1) and c(x_2) will also not be equal. In symbols:

x_1 \neq x_2 \Rightarrow c(x_1) \neq c(x_2)

Notice how this is phrased negatively, in terms of things being not equal to each other. It is usually much easier to prove the contrapositive of this statement, namely

c(x_1) = c(x_2) \Rightarrow x_1 = x_2

That is, if x_1 and x_2 map to the same remainders (a,b), then x_1 and x_2 must in fact be the same. This is logically equivalent (you should try to convince yourself of this if you’re unsure!) but much easier to get a handle on.

So, suppose we have numbers x_1 and x_2, both non-negative and less than mn, and suppose they give the same results \pmod m and \pmod n, that is, x_1 \equiv x_2 \equiv a \pmod m and x_1 \equiv x_2 \equiv b \pmod n. Consider their difference d = x_2 - x_1. Since x_1 and x_2 have the same remainder when divided by m, it must be the case that d is evenly divisible by m; likewise, d is evenly divisible by n. But since m and n are relatively prime, that is, they share no common factors, they cannot overlap at all in d’s prime factorization; so in fact d must be divisible by their product, mn. In theory, then, d could be one of the values -2mn, -mn, 0, mn, 2mn, 3mn\dots. Which is it? Well, remember that d = x_2 - x_1, and 0 \leq x_1, x_2 < mn. Subtracting two nonnegative integers less than mn could never produce any multiple of mn other than 0. So in fact d = x_2 - x_1 = 0, which means x_1 = x_2.

So the function c is one-to-one. But it maps between two finite sets of the same size—namely, [mn] and [m] \times [n], both of which have exactly mn elements. If a function between two finite sets of the same size is one-to-one, it must actually be a bijection. That is, if we have the same number of things on each side, and a way to send each item on the left to a distinct item on the right, then we in fact have a way to match up every element on both sides with exactly one on the other side.

As a final note, this proof certainly has simplicity going for it, but you may find it a bit unsatisfactory: although it tells us that the function c has an inverse, it doesn’t tell us how to compute it. That is, given a particular pair of remainders (a,b) where x \equiv a \pmod m and x \equiv b \pmod n, how do we find x? It can certainly be done. But for now I will let you look it up, and perhaps I’ll write about it at some point in the future!

Posted in modular arithmetic, number theory | Tagged , , , | 2 Comments

More words about PWW #25: The Chinese Remainder Theorem

In a previous post I made images like this:

And then in the next post I explained how I made the images: starting in the upper left corner of a grid, put consecutive numbers along a diagonal line, wrapping around both from bottom to top and right to left. The question is then why some grids get completely filled in, like the one above, and why some have holes, like this:

Commenter ZL got the right answer: the grid will be completely filled in if and only if the width and height of the grid are relatively prime.

In fact, this is (a special case of1) the Chinese remainder theorem (as commenter Jon Awbrey foresaw). In more traditional terms, the Chinese remainder theorem says that if we have a system of two modular equations

\begin{array}{rcl}x &\equiv& a \pmod m \\ x &\equiv& b \pmod n\end{array}

then as long as m and n are relatively prime, there is a unique solution for x in the range 0 \leq x < mn.

Here’s another way to think about this. Suppose I have a number x in the range 0 \leq x < mn. If I tell you only x \bmod m, that is, the remainder when dividing x by m, you can’t tell for sure what x is; there may be multiple possibilities for x. Likewise, if I only tell you x \bmod n, you don’t know x. But if I tell you both—as long as m and n are relatively prime—it’s enough information to precisely pin down the value of x; there is only one value of x which has a certain remainder modulo m and at the same time a certain remainder modulo n.

Yet another way to state the theorem is to consider the function

c(x) = (x \bmod m, x \bmod n)

which sends an integer x \in \{0, \dots, mn-1\} to a pair of integers where the first is in the range \{0, \dots, m-1\} and the second is in the range \{0, \dots, n-1\}. If we use the notation [n] = \{0, \dots, n-1\} then we can write this concisely as

c : [mn] \to [m] \times [n]

The Chinese Remainder Theorem just says that this function is actually a bijection, that is, it is onto (every pair (a,b) has some solution x such that c(x) = (a,b)) and one-to-one (the x for a given (a,b) is unique).

But this function c is exactly what the grid diagrams are visualizing! We start at x = 0 in the upper left, and every time we step to the next value of x, we take a step down; so in general the number x will be on row x (if we number the rows starting with row 0 at the top)—except that we wrap around when we get to the bottom. So if there are m rows, that means x will be on row x \bmod m. Similarly, we take a step to the right with each next value of x, and wrap around; so x will be in column x \bmod n. Hence each x will end up at grid coordinates (x \bmod m, x \bmod n), which is exactly the function c. And c being a bijection is exactly the same thing as the grid being completely filled in: every value of x corresponds to a different grid square, and every grid square has a value of x.

In my next post I’ll go over a simple proof of the theorem.


  1. The full Chinese Remainder Theorem actually says something about the situation where you have an arbitrary number of these equations, not just two; but the version with only two equations has all the essential features. (Indeed, once you believe the version with two equations, you can “bootstrap” your way to dealing with an arbitrary number just by applying the two-equation version repeatedly.)

Posted in modular arithmetic, number theory, posts without words | Tagged , , , , | 3 Comments

33 is the sum of three cubes

I’m a bit late to the party, but I find this fascinating: we now know (thanks to a discovery of Andrew R. Booker) that the number 33 can be written as the sum of three cubes. This may sound unremarkable, but it has been unknown for a long time whether this was possible. Part of the reason this is more difficult than it sounds is that cubes can be both positive and negative.

By contrast, it is very easy to decide whether it is possible to write 33 as a sum of two squares, 33 = a^2 + b^2. Since squares can only be positive, any values of a and b greater than 5 are not going to work, since they would make the sum too big. So there are only a few pairs of values to check: it’s enough to just check all pairs (a,b) with 1 \leq a \leq b \leq 5 (quick: how many such pairs are there?), which can even be done by hand in a few minutes. None of them work, so this exhaustive search of all the possibilities proves that it is not possible to find a and b such that 33 = a^2 + b^2.

But a sum of three cubes, 33 = a^3 + b^3 + c^3, is an entirely different matter! We can’t put any a priori bound on the size of the values a, b, and c, because the cube of a negative number is negative—if we choose at least one of them to be positive and at least one of them to be negative, they could in theory be very large but “cancel out” to yield 33. And that’s exactly what Dr. Booker found (using approximately 23 years’ worth of computer time spread over one month!):

33 = 8\,866\,128\,975\,287\,528^3 + (-8\,778\,405\,442\,862\,239)^3 + (-2\,736\,111\,468\,807\,040)^3.

Whoa.

Posted in number theory | Tagged , , | Leave a comment