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
then as long as and are relatively prime, there is a unique solution for in the range .
Here’s another way to think about this. Suppose I have a number in the range . If I tell you only , that is, the remainder when dividing by , you can’t tell for sure what is; there may be multiple possibilities for . Likewise, if I only tell you , you don’t know . But if I tell you both—as long as and are relatively prime—it’s enough information to precisely pin down the value of ; there is only one value of which has a certain remainder modulo and at the same time a certain remainder modulo .
Yet another way to state the theorem is to consider the function
which sends an integer to a pair of integers where the first is in the range and the second is in the range . If we use the notation then we can write this concisely as
The Chinese Remainder Theorem just says that this function is actually a bijection, that is, it is onto (every pair has some solution such that ) and one-to-one (the for a given is unique).
But this function is exactly what the grid diagrams are visualizing! We start at in the upper left, and every time we step to the next value of , we take a step down; so in general the number will be on row (if we number the rows starting with row at the top)—except that we wrap around when we get to the bottom. So if there are rows, that means will be on row . Similarly, we take a step to the right with each next value of , and wrap around; so will be in column . Hence each will end up at grid coordinates , which is exactly the function . And being a bijection is exactly the same thing as the grid being completely filled in: every value of corresponds to a different grid square, and every grid square has a value of .
In my next post I’ll go over a simple proof of the theorem.
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.)↩
Pingback: Chinese Remainder Theorem proof | The Math Less Traveled
Pingback: Computing the Euler totient function, part 2: seeing phi is multiplicative | The Math Less Traveled
Pingback: Computing the Euler totient function, part 3: proving phi is multiplicative | The Math Less Traveled