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.


Posted in number theory | Tagged , ,

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

Post without words #25

Image | Posted on by | Tagged | 4 Comments

Goldilogs and the n bears

Once upon a time there was a girl named Goldilogs. As she was walking through the woods one day, she came upon a curious, long house. Walking all round it and seeing no one at home, she tried the door and found that it was open. Inside, she saw a very long row of chairs. She tried sitting in the first chair, but it was too small for her. So she tried sitting in the second chair, but it was also too small. The third chair was too small as well. “Oh dear,” said Goldilogs. “This is going to take all day.”

But then Goldilogs noticed that the chairs were arranged in order, from smallest to largest, and she clapped her hands with delight. “What organized people must live here!” she exclaimed. “I wonder, how ever did they arrange their chairs this way?” So she tried the chair in the middle of the row, and it was too big. Next she tried the chair a quarter of the way along, and it was too small. She continued in this manner, eliminating half of the remaining chairs with each test, until finally she found one that was Just Right. In fact, she found it so quickly that she had plenty of time to sit and enjoy reading from the selection of algorithms textbooks that she found on a shelf, and then she put everything back the way she found it and left before the bears got home.

Posted in computation, humor | Tagged , , , , | 1 Comment

Finding the repetend length of a decimal expansion

We’re still trying to find the prefix length k and repetend length n of the decimal expansion of a fraction a/b, that is, the length of the part before it starts repeating, and the length of the repeating part. In my previous post we found that the prefix length k is fairly simple to find: it’s equal to the maximum number of factors of either 2 or 5 in b.

What about n? This is a bit tricker to do efficiently. Let b' denote the result after removing all factors of 2 or 5 from b, as before. Then we want (10^n - 1) to be evenly divisible by b', or put another way, we want the smallest n such that

10^n \equiv 1 \pmod {b'}.

So the obvious method is to compute 10 \bmod {b'}, 10^2 \bmod {b'}, 10^3 \bmod {b'}, and so on, and find the first which yields 1. Practically speaking, we don’t have to compute 10^n from scratch at each step: we can start with 1, and then at each step multiply the current value by 10 and reduce \pmod {b'}. We keep doing this until we reach 1 again, and record how many steps it took. For example,

\begin{array}{rcl} 10 &\equiv & 10 \pmod{21} \\ 10 \cdot 10 = 100 &\equiv & 16 \pmod{21} \\ 16 \cdot 10 = 160 &\equiv & 13 \pmod{21} \\ 13 \cdot 10 = 130 &\equiv & 4 \pmod{21} \\ 4 \cdot 10 = 40 &\equiv & 19 \pmod{21} \\ 19 \cdot 10 = 190 &\equiv & 1 \pmod{21} \end{array}

This took 6 steps, therefore n = 6 is the smallest n such that 10^n - 1 is divisible by 21; this matches what we saw in the previous posts, for example, the fact that 89/420 has a repetend length of 6 (remember that removing factors of 2 and 5 from 420 yields 21).

This method is correct, but we can do better—although for this we’ll need a little bit of group theory!

  • Recall that \Phi(b') is the set of numbers between 1 and b'-1 (inclusive) which share no common factors with b'.
  • \Phi(b') actually forms a group under multiplication \pmod {b'}: multiplying two values of \Phi(b') always yields another such value, and for every x \in \Phi(b') there is some y \in \Phi(b') such that xy \equiv 1 \pmod{b'}.
  • We are then really asking for the order of the element 10 in the group \Phi(b').
  • By Lagrange’s Theorem, the order of an element must evenly divide the order of the group.
  • The order of a group is just its size; in this case the order of \Phi(b') is \varphi(b'), the Euler totient function of b'.
  • Hence we have learned that n—the order of 10 in the group \Phi(b')—must evenly divide \varphi(b').

We can use this knowledge to find n more quickly than simply counting powers of 10: just list all the divisors of \varphi(b'), try each one by raising 10 to the power of the divisor \pmod {b'} (using fast modular exponentiation of course), and pick the smallest one that yields 1. Using our example from before of b' = 21, we find that \varphi(21) = (3-1)(7-1) = 12, and so n has to be one of 1, 2, 3, 4, 6, or 12. As another, bigger example, suppose b' = 3^5 \cdot 7 \cdot 89 = 151389. Then we can compute

\varphi(b') = (3-1) \cdot 3^4 \cdot (7-1) \cdot (89-1) = 2^5 \cdot 3^5 \cdot 11 = 85536.

(I was going to link to an explanation of how to compute \varphi—but it seems although I’ve mentioned \varphi many times before, I’ve never actually written about how to compute it! I’ll have to do that soon, since it’s a very interesting topic. In any case, if you don’t know how, you can just take my word for now.) This number has 6 \cdot 6 \cdot 2 = 72 divisors we would have to try (since to make a divisor of 2^5 \cdot 3^5 \cdot 11, there are 6 choices for the exponent of 2 (namely, 0 through 5), 6 choices for the exponent of 3, and 2 choices for the exponent of 11). 72 things to try is much, much better than trying every single possible value from 1 up to 151388! I wrote a little computer program to try them all, and it turns out that n = 1188 = 2^2 \cdot 3^3 \cdot 11^1 is the smallest divisor that works. Hence, we find that 1/151389 has a repetend of length 1188 (but I’m sure you knew that already =).

It turns out we can do this computation even faster—but that will have to wait for another post!

Posted in computation, group theory, modular arithmetic, number theory, pattern | Tagged , , , , , ,