The Chinese Remainder Theorem

Find all integers that leave a remainder of $1$ when divided by $2$, $3$, and $5$.

You might like to think about this problem for yourself before reading on.

Here is one way to solve the problem. Let $x$ be an integer that leaves a remainder of $1$ when divided by $2$, $3$ and $5$. Then $x-1$ is divisible by $2$, $3$ and $5$. Since $2$, $3$ and $5$ are coprime (have no common factors greater than $1$), any number that is divisible by all of them must be divisible by their product, which is $30$. So if $x$ has the required properties then $x-1$ is divisible by $30$. This means that we can write $x$ in the form $30k+1$ (for some integer $k$).

It remains to check that all such integers work. But if $x=30k+1$ then $x=2\times 15k+1=3\times 10k+1=5\times 10k+1$ leaves a remainder of $1$ when divided by $2$, $3$, and $5$. The answer to the question is therefore all numbers of the form $30k+1$, where $k$ is an integer.

So far, so good. We have solved the question. Here is another problem like this.

Find all integers that leave a remainder of $3$ when divided by $5$, a remainder of $5$ when divided by $7$, and a remainder of $7$ when divided by $11$.

Again, try this problem for yourself before you read on.

Whilst similar ideas to those used above will work here, it's getting a bit trickier. In fact, it's not even obvious that there are any solutions here. What we'd like is an approach that is easier to generalise, so that it will be easier to apply it to other questions (and, indeed, to a general case involving algebra, which is what the Chinese Remainder Theorem does).

Let's first introduce some notation, so that we don't have to keep writing "leaves a remainder of ...when divided by''. If $x-y$ is divisible by $n$, then write $x\equiv y\pmod{n}$. In particular, if $x$ leaves a remainder of $y$ when divided by $n$, then we shall write $x\equiv y$ (mod $n$). Read this as "$x$ is congruent to $y$ mod $n$''. You can read more about this in the NRICH article on Modular Arithmetic, but you don't need to have read that article in order to understand this article.

In the new notation, we can write our problem as

Find all integers $x$ such that

Let's invent a way to illustrate this. We'll have axes corresponding to the numbers by which we are dividing. For example,

Image

We represent the number $17$ on this graph by the point $(2,3,6)$, since $17\equiv 2\pmod{5}$, $17\equiv 3\pmod{7}$, and $17\equiv 6\pmod{11}$. Of course, there are lots of numbers that all correspond to the same point. For example, $402\equiv 2\pmod{5}$, $402\equiv 3\pmod{7}$, and $402\equiv 6\pmod{11}$, so $402$ and $17$ both correspond to $(2,3,6)$. (You might like to think about why this is - we'll return to this soon.)

What we want to do is to find all the numbers corresponding to the point $(3,5,7)$.

Let's pause for a moment. Suppose that we have found two numbers, say $x$ and $y$, that both correspond to the point $(3,5,7)$. That is, $x\equiv 3\equiv y\pmod{5}$, and $x\equiv 5\equiv y\pmod {7}$, and $x\equiv 7\equiv y\pmod{11}$. Then $5$ divides $x-y$, and $7$ divides $x-y$, and $11$ divides $x-y$. Since $5$, $7$ and $11$ are coprime, we see that $5\times 7\times 11=385$ divides $x-y$. So if we have two solutions, then they must differ by a multiple of $385$. In fact, if $x$ is a solution, then so is $x+385k$, for any integer $k$. Check this yourself - it's not too hard. (Notice that the two numbers that I picked earlier that both correspond to the point $(2,3,6)$ differ by $402-17=385$.)

What this tells us is that we only need to find one solution, as we can then find all the others by adding and subtracting multiples of $385$. So we shall concentrate our attention on finding one number that corresponds to the point $(3,5,7)$.

Suppose that I have a number $x$ that corresponds to the point $(a,b,c)$, and a number $y$ that corresponds to the point $(l,m,n)$. Then $x+y$ corresponds to the point $(a+l,b+m,c+n)$ (reducing $a+l$ mod $5$, $b+m$ mod $7$ and $c+n$ mod $11$ where necessary). Also, if $k$ is any integer, then $k x$ corresponds to the point $(k a, k b, k c)$ (again reducing co-ordinates where necessary). You should check these statements yourself, using the definition of what it means for a number to correspond to a point.

This means that if we have a number $x_1$ corresponding to the point $(1,0,0)$, a number $x_2$ corresponding to $(0,1,0)$, and a number $x_3$ corresponding to $(0,0,1)$, then $3x_1+5x_2+7x_3$ will be a number corresponding to the point $(3,5,7)$. In fact, if we can find the numbers $x_1$, $x_2$ and $x_3$, then we'll be able to find numbers corresponding to all points, which would be rather good! So let's find $x_1$, $x_2$ and $x_3$.

We want $x_1$ that satisfies $x_1\equiv 1\pmod{5}$, $x_1\equiv 0\pmod{7}$, and $x_1\equiv 0\pmod{11}$.

The last two congruences tell us that $x_1$ must be divisible by both $7$ and $11$, so must be $x_1=77x_1\prime$ for some integer $x_1\prime$.

We are now left with the task of finding $x_1\prime$ such that $77x_1\prime\equiv 1\pmod{5}$, i.e., $2x_1\prime \equiv 1\pmod{5}$. Multiplying both sides by $3$ (and using the fact that $2\times 3\equiv 6\equiv 1\pmod{5}$, we get $x_1\prime\equiv 3\pmod{5}$. Let's try $x_1\prime\equiv 3$.

Then $x_1=231$, and $x_1$ has the properties we want.

In a very similar way, we get $x_2=330$ and $x_3=210$.

From this, we obtain $3x_1+5x_2+7x_3=3\times 231+5\times 330+7\times 210 =693+1650+1470=3813$. By the above, we know that we may subtract multiples of $385$, so the smallest positive solution is $x=348$, and the integer solutions are all the numbers of the form $348+385k$, where $k$ is an integer.

Before we move on to the general situation, let's consider whether we can always find a number corresponding to the point $(1,0,0)$ (regardless of the moduli on the axes). The answer is of course "no". For example, if I have $2$ on the $x$-axis and $4$ on the $y$-axis, then I cannot find a number corresponding to $(1,0,0)$, as it would have to be congruent to $1\pmod{2}$ (that is, odd) and congruent to $0\pmod{4}$ (that is, divisible by $4$), which is clearly absurd.

Now let's move on to the Chinese Remainder Theorem itself.

Let $p_1$, $p_2$, ... , and $p_n$ be distinct primes. For any integers $a_1$, $a_2$, ... , $a_n$, there is an integer $x$ with and $x$ is unique mod $p_1p_2 \ldots p_n$.

Don't panic about the "unique mod $p_1 p_2 \ldots p_n$'' bit. All this means is that all of the solutions differ by multiples of $p_1 p_2 \ldots p_n$.

You might like to compare this to what we have already seen above, when we had $p_1=5$, $p_2=7$, $p_3=11$, $a_1=3$, $a_2=5$, and $a_3=7$.

We shall use the same idea as last time - but without drawing a set of axes in $n$ dimensions!

Firstly, let's do the uniqueness part.

Suppose that we have two solutions, $x$ and $y$.

Then $x\equiv y\pmod{p_1}$, and $x\equiv y\pmod{p_2}$, and ... , and $x\equiv y\pmod{p_n}$, so $x$ and $y$ differ by a multiple of $p_1p_2 \ldots p_n$.

Also, if $x$ is a solution and $k$ is an integer, then $x+p_1 p_2 \ldots p_n k$ is also a solution.

So the solutions all differ by multiples of $p_1 p_2 \ldots p_n$, as we wanted.

Now let's try to prove that there is a solution!

Using the same ideas as before, let's suppose that we can find numbers $x_1$, $x_2$, ... , and $x_n$ in such a way that $x_i$ corresponds to the point with $i^{\textrm{th}}$ co-ordinate equal to $1$, and the other co-ordinates all $0$.

Then $x=a_1 x_1 + a_2 x_2 + \ldots +a_n x_n$ is a solution to the congruences as required.

For example, mod $p_1$ none of the $x_2$, ... , $x_n$ parts contribute (as they are all congruent to $0$ (mod $p_1$) , so $x\equiv a_1 x_1 \equiv a_1\pmod{p_1}$ (as $x_1\equiv 1$ (mod $p_1$)), and similarly for $p_2$, $p_3$, ... , and $p_n$.

We now just need to find $x_1$, $x_2$, ... , and $x_n$ with the given properties. For example, we need $x_1$ such that We shall need $x_1$ to be divisible by all of $p_2$, $p_3$, ...and $p_n$. So we can write it as $x_1=p_2 p_3 \ldots p_n x_1\prime$ for some integer $x_1\prime$.

Now we need $p_2 p_3 \ldots p_n x_1\prime\equiv 1\pmod{p_1}$. It is a result of number theory that (because $p_1$ shares no factors greater than $1$ with $p_2$, $p_3$, ... , or $p_n$) we may solve this. You can find an explanation of this in the NRICH article Modular Arithmetic , but if you are willing to take the result on trust for now then you can save the article for later! We can find $x_2$, $x_3$, ...and $x_n$ in the same way, and so we have the required numbers.

Since we can find $x_1$,$x_2$, ...and $x_n$, we can find $x=a_1 x_1+ a_2 x_2 + \ldots +a_n x_n$ that solves the congruences, and, since we can find our solution we can, by our earlier work on uniqueness, find all the integer solutions, and so our proof is complete.

In fact, we can be a bit more general than this. For example, it is sufficient for $p_1$, $p_2$, ...and $p_n$ to be pairwise coprime (no two have a common factor greater than $1$) rather than just prime, and the proof proceeds in the same way.

You might like to look at two related problems on the NRICH site: Remainders and One O Five .