Skip to main content
Logo image

Section 5.4 Using the Chinese Remainder Theorem

We will here present a completely constructive proof of the CRT (Theorem 5.3.2). That is, we will not just prove it can be done, we will show how to get a solution to a given system of linear congruences.
Keep in mind that this is a procedure that works. It may have a number of steps, but its power is not to be underestimated. After some careful examples, we’ll see some other uses.

Subsection 5.4.1 Constructing simultaneous solutions

Remember that we are trying to solve the system of equations \(x\equiv a_i\) (mod \(n_i\)). It is important to confirm that all \(n_i\) are coprime in pairs (or that the set of moduli is mutually coprime, Definition 2.4.9). Then the following steps will lead to a solution. You will find basically this proof in any text; I use the notation in [E.2.1], while that in [E.2.4] basically uses the letter m instead of n.
Clearly this needs an example.

Example 5.4.2. A first CRT example.

Let’s look at how to solve our original system from Question 5.3.1 using this method. First we write our simultaneous congruences:
  • \(x\equiv 1\) (mod \(5\))
  • \(x\equiv 2\) (mod \(6\))
  • \(x\equiv 3\) (mod \(7\))
We’ll follow along with each of the steps in Sage. First, I’ll make sure I know all my initial constants (printing them to verify). This is step 1.
Next, I’ll put down all the \(c_i\text{,}\) the complements to the moduli, so to speak. Remember, \(c_i=N/n_i\text{.}\) This is step 2 above.
Now we need to solve for the inverse of each \(c_i\) modulo \(n_i\text{.}\) One could do this by hand. For instance,
\begin{equation*} 42d_1\equiv 2d_1\equiv 1\text{ (mod }5)\text{ yielding }d_1=3,\text{ since }2\cdot 3=6\equiv 1\text{ (mod }5)\text{.} \end{equation*}
But that is best done on homework for careful practice; in the text, we might as well use the power of Sage.
That was step 3. Now I’ll create each of the big product numbers, as well as their sum, which is steps 4 and 5.
Of course, we don’t recognize \(836\) as our answer. But that is because the solution is only unique modulo \(N\text{:}\)
Now we see our friend \(206\text{,}\) as expected if you successfully tried Question 5.3.1.

Sage note 5.4.3. Printing it out.

When using Sage cells, you might not want only the things in the last line returned to you as output. You can use the print function to get them to print out, as we have done in the preceding example 5.4.2.
This is actually capability in Python itself, not just Sage, so if you have previous experience with Python (or perhaps other languages), it is very important to note print() is a function. That means the thing to be printed must be in parentheses, such as print(3). Previously (in Sage versions previous to 9.0, and anything else based on Python 2) syntax such as print 3 was allowed, and experienced Sage users may need some time to adjust. If you are new to Sage, no worries!

Example 5.4.4.

Let’s try some more interesting moduli for an example to do on your own. Can you follow the template?
  • \(x\equiv 1\) (mod \(6\))
  • \(x\equiv 11\) (mod \(35\))
  • \(x\equiv 3\) (mod \(11\))
Sage can also approach this in a similar way, as we saw earlier.

Subsection 5.4.2 A theoretical but highly important use of CRT

The following proposition is an example of one of the many useful things we can do with the CRT.
As a result, any question about a congruence is really a question about several congruences, but with smaller moduli (indeed, simpler moduli in a specific sense; see Proposition 6.5.1 for a strong statement of this). We will use this fact again and again in the remainder of the text, and it is a huge reason why the Chinese Remainder Theorem is so intensely powerful.