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 , , | Leave a 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 , , , , | 2 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.


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

A few words about PWW #25

In my previous post I made images like this:

What’s going on? Well, first, it’s easy to notice that each grid starts with 0 in the upper-left square; 1 is one square down and to the right of 0, then 2 is one square down and to the right of 1, and so on….

When we get to an edge, we “wrap around” from the bottom to the top and/or from the right to the left. For example, in the grid above, notice how the 4 is still one space to the right of the 3, but in the top row; likewise, the 7 is below the 6 but in the left column; then the 8 immediately wraps back around to the top row, and so on.

In other words, we can imagine that we are really making a straight diagonal line, but the bottom edge of the grid is “glued” to the top edge, and the right edge is glued to the left edge (making a torus, aka donut).

Equivalently, we can imagine gluing a bunch of copies of the grid together along their edges, and the numbers just count in a straight diagonal line, moving from one grid to the next, like this:

Although really, since each grid is supposed to be a copy, we should draw a diagonal sequence of numbers starting at 0 in the upper-left corner of every copy!

So in this particular example, if we keep doing this, we eventually fill up the entire grid/space:

But sometimes that doesn’t happen; for example:

In this example, when we get to the 5 in the bottom-right corner, we would have to wrap around to the top left again, but the 0 is already there. So the process stops before we actually fill up the whole grid. This is why some of the grids have empty spaces in them. Here’s another slightly more interesting example:

So, what’s the difference? How can you tell whether a particular grid is going to fill up or have empty spaces left over?

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