Section5.4Using the Chinese Remainder Theorem¶ permalink

We will here present a completely constructive proof of the CRT (Theorem 5.3.1). 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.

Subsection5.4.1Constructing simultaneous solutions¶ permalink

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. Then the following steps will lead to a solution. You will find basically this proof in any text; I use the notation in [C.1.1].

First, let's call the product of the moduli $n_1 n_2 \cdots n_k=N$ .
Take the quotient $N/n_i$ and call it $c_i$ . It's sort of a “complement” to the $i$ th modulus within the big product $N$ .
Now find the inverse of each $c_i$ modulo $n_i$ . That is, for each $i$ , find a solution $d_i$ such that $\begin{equation*}c_i d_i\equiv 1\text{ (mod }n_i)\end{equation*}$

Notice that this is possible. You can't find an inverse modulo any old thing! But in this case, $c_i$ is the product of a bunch of numbers, all of which are coprime to $n_i$ , so it is also coprime to $n_i$ , as required.
For each $i$ , multiply the three numbers $a_i \cdot c_i \cdot d_i$ .
Now we evaluate each of these products (indexed by $i$ ) modulo the various $n_j$ . That looks bad, but most things cancel:
- By definition, each $c_j$ is divisible by $n_i$ (except for $c_i$ itself), so modulo $n_i$ the product is $\begin{equation*}a_j c_j d_j \equiv 0\text{ (mod }n_i)\; .\end{equation*}$
- The product $\begin{equation*}a_i c_i d_i \equiv a_i \cdot 1\equiv a_i\text{ (mod }n_i)\end{equation*}$
Now add all these products together to get our final answer, $\begin{equation*}x=a_1 c_1 d_1+a_2 c_2 d_2+\cdots +a_k c_k d_k\; .\end{equation*}$ For each $n_i$ , we can do the sum modulo $n_i$ too; the previous step shows this sum is $\begin{equation*}x\equiv 0+0+\cdots +a_i +\cdots +0\text{ (mod }n_i)\; .\end{equation*}$ So this is definitely a solution.
Any other solution $x'$ has to still fulfill $x'\equiv a_i\equiv x$ (mod $n_i$ ), so $n_i\mid x'-x$ for all moduli $n_i$ . Since all $n_i$ are relatively prime to each other, $N\mid x'-x$ too (if $a\mid c$ and $b\mid c$ and $\gcd(a,b)=1$ , then $ab\mid c$ ). So $x'\equiv x$ (mod $N$ ), which means $x$ is the only solution modulo $N$ !

Clearly this needs an example.

Example5.4.1A first CRT example

Let's look at how to solve our original system using this method.

$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.

xxxxxxxxxx
 
n_1, n_2, n_3 = 5,6,7
a_1, a_2, a_3 = 1,2,3
N = n_1*n_2*n_3
print n_1, n_2, n_3
print a_1, a_2, a_3
print N

Next, I'll write down all the $c_i$ , the complements to the moduli, so to speak. Remember, $c_i=N/n_i$ .

xxxxxxxxxx
 
n_1, n_2, n_3 = 5,6,7
a_1, a_2, a_3 = 1,2,3
N = n_1*n_2*n_3
c_1,c_2,c_3 = N/n_1,N/n_2,N/n_3; c_1,c_2,c_3

Now we need to solve for the inverse of each $c_i$ modulo $n_i$ . 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)\; .\end{equation*}$ But that is best done on homework for careful practice; in the text, we might as well use the power of Sage.

xxxxxxxxxx
 
d_1=inverse_mod(42,5); d_2=inverse_mod(35,6);d_3=inverse_mod(30,7)
d_1,d_2,d_3

Now I'll create each of the big product numbers, as well as their sum.

xxxxxxxxxx
 
n_1, n_2, n_3 = 5,6,7
a_1, a_2, a_3 = 1,2,3
N = n_1*n_2*n_3
d_1=inverse_mod(42,5); d_2=inverse_mod(35,6); d_3=inverse_mod(30,7)
a_1*c_1*d_1, a_2*c_2*d_2,a_3*c_3*d_3; a_1*c_1*d_1+a_2*c_2*d_2+a_3*c_3*d_3

Of course, we don't recognize 836 as our answer. But:

xxxxxxxxxx
 
n_1, n_2, n_3 = 5,6,7
N = n_1*n_2*n_3
mod(836,N)

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.

xxxxxxxxxx
 
@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']])
def _(a_1=('\(a_1\)',1), a_2=('\(a_2\)',2), a_3=('\(a_3\)',3), n_1=('\(n_1\)',5), n_2=('\(n_2\)',6), n_3=('\(n_3\)',7)):
    try:
        answer = []
        for i in [1..n_1*n_2*n_3]:
            if (i%n_1 == a_1) and (i%n_2 == a_2) and (i%n_3 == a_3):
              answer.append(i)
        string1 = "<ul><li>$x\equiv %s \\text{ (mod }%s)$</li>"%(a_1,n_1)
        string2 = "<li>$x\equiv %s \\text{ (mod }%s)$</li>"%(a_2,n_2)
        string3 = "<li>$x\equiv %s \\text{ (mod }%s)$</li></ul>"%(a_3,n_3)
        pretty_print(html("The simultaneous solutions to "))
        pretty_print(html(string1+string2+string3))
        if len(answer)==0:
            pretty_print(html("are none"))
        else:
            pretty_print(html("all have the form "))
            for ans in answer:
                pretty_print(html("$%s$ modulo $%s$"%(ans,n_1*n_2*n_3)))
    except ValueError, e:
        pretty_print(html("Make sure the moduli are appropriate for solving!"))
        pretty_print(html("Sage gives the error message:"))
        pretty_print(html(e))

Subsection5.4.2A theoretical but highly important use of CRT

Now, there are many, many useful things we can do with the CRT.

Proposition5.4.2Converting to and from coprime moduli

Suppose that $X\equiv Y$ (mod $N$ ), and $N=\prod m_i$ , where $\gcd(m_i,m_j)=1$ for all $i\neq j$ . Then we have two directions of equivalence between a congruence and a system of congruences.

Certainly if $N$ divides $X-Y$ , so does a factor of $N$ , so $X\equiv Y$ (mod $m_i$ ) for each of the relatively prime factors of $N$ . Thus, solutions to the “big” congruence are also solutions to a system of many little ones.
But the CRT allows me to reverse this process. The moduli in question are all coprime to each other, so if we are given a solution pair $(X_i,Y_i)$ to each of the congruences $\begin{equation*}X_i\equiv Y_i\text{ (mod }m_i) \end{equation*}$ then when combined they will give one (!) solution of $\begin{equation*}X\equiv Y\text{ (mod }N\text{)}\end{equation*}$

That means that any question about congruences is really a question about congruences modulo simple moduli (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.