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×15k+1=3×10k+1=5×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 º y (mod n). In particular, if x leaves a remainder of y when divided by n, then we shall write x º 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

x º 3 (mod 5)  and x º 5 (mod 7)  and x º 7 (mod 11) .

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

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 º 3 º y (mod 5), and x º 5 º y (mod 7), and x º 7 º y (mod 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×7×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₁ corresponding to the point (1,0,0), a number x₂ corresponding to (0,1,0), and a number x₃ corresponding to (0,0,1), then 3x₁+5x₂+7x₃ will be a number corresponding to the point (3,5,7). In fact, if we can find the numbers x₁, x₂ and x₃, then we'll be able to find numbers corresponding to all points, which would be rather good! So let's find x₁, x₂ and x₃.

We want x₁ that satisfies x₁ º 1 (mod 5), x₁ º 0 (mod 7), and x₁ º 0 (mod 11).

The last two congruences tell us that x₁ must be divisible by both 7 and 11, so must be x₁=77x₁¢ for some integer x₁¢.

We are now left with the task of finding x₁¢ such that 77x₁¢ º 1 (mod 5), i.e., 2x₁¢ º 1 (mod 5). Multiplying both sides by 3 (and using the fact that 2×3 º 6 º 1 (mod 5)), we get x₁¢ º 3 (mod 5). Let's try x₁¢ º 3.

Then x₁=231, and x₁ has the properties we want.

In a very similar way, we get x₂=330 and x₃=210.

From this, we obtain 3x₁+5x₂+7x₃=3×231+5×330+7×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 (mod 2) (that is, odd) and congruent to 0 (mod 4) (that is, divisible by 4), which is clearly absurd.

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

Theorem Let p₁, p₂, ..., and p_n be distinct primes. For any integers a₁, a₂, ..., a_n, there is an integer x with

x º a1 (mod p1) x º a2 (mod p2) ¼ x º an (mod pn),

and x is unique mod p₁p₂ ¼p_n.

Don't panic about the``unique mod p₁ p₂ ¼p_n'' bit. All this means is that all of the solutions differ by multiples of p₁ p₂ ¼p_n.

You might like to compare this to what we have already seen above, when we had p₁=5, p₂=7, p₃=11, a₁=3, a₂=5, and a₃=7.

Proof 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 º y (mod p₁), and x º y (mod p₂), and ..., and x º y (mod p_n), so x and y differ by a multiple of p₁p₂ ¼p_n.

Also, if x is a solution and k is an integer, then x+p₁ p₂ ¼p_n k is also a solution.

So the solutions all differ by multiples of p₁ p₂ ¼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₁, x₂, ..., and x_n in such a way that x_i corresponds to the point with i^th co-ordinate equal to 1, and the other co-ordinates all 0.

Then x=a₁ x₁ + a₂ x₂ + ¼+a_n x_n is a solution to the congruences as required.

For example, mod p₁ none of the x₂, ..., x_n parts contribute (as they are all congruent to 0 (mod p₁)), so x º a₁ x₁ º a₁ (mod p₁) (as x₁ º 1 (mod p₁)), and similarly for p₂, p₃, ..., and p_n.

We now just need to find x₁, x₂, ..., and x_n with the given properties. For example, we need x₁ such that

x1 º 1 (mod p1)  and x1 º 0 (mod p2)  and ¼ and x1 º 0 (mod pn).

We shall need x₁ to be divisible by all of p₂, p₃, ... and p_n. So we can write it as x₁=p₂ p₃ ¼p_n x₁¢ for some integer x₁¢.

Now we need p₂ p₃ ¼p_n x₁¢ º 1 (mod p₁). It is a result of number theory that (because p₁ shares no factors greater than 1 with p₂, p₃, ..., 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₂, x₃, ... and x_n in the same way, and so we have the required numbers.

Since we can find x₁,x₂, ... and x_n, we can find x=a₁ x₁+ a₂ x₂ + ¼+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₁, p₂, ... 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.