NTIC Using the Chinese Remainder Theorem

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.

🔗

Algorithm 5.4.1.

The following steps not only yield the solution, but mostly indicate the proof as well.

First, let's call the product of the moduli $n_1 n_2 \cdots n_k=N\text{.}$
Take the quotient $N/n_i$ and call it $c_i\text{.}$ It's sort of a “complement” to the $i$ th modulus within the big product $N\text{.}$
Now find the inverse of each $c_i$ modulo $n_i\text{.}$ That is, for each $i\text{,}$ 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\text{,}$ so it is also coprime to $n_i\text{,}$ as required.
For each $i\text{,}$ multiply the three numbers $a_i \cdot c_i \cdot d_i\text{.}$
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\text{.} \end{equation*}$

What remains is to verify that this works. Go back to the last two steps.

Let us evaluate each of the products in the penultimate step (indexed by $i$ ) modulo the various $n_j\text{.}$ That looks bad, but most things cancel because each $c_j$ is divisible by $n_i$ (except for $c_i$ itself).
- When $i\neq j\text{,}$ the product modulo $n_i$ is thus
  
  $\begin{equation*} a_j c_j d_j \equiv 0\text{ (mod }n_i)\text{.} \end{equation*}$
- Otherwise we can use the definition of inverse, and the product is
  
  $\begin{equation*} a_i c_i d_i \equiv a_i \cdot 1\equiv a_i\text{ (mod }n_i) \end{equation*}$
To check the final step, for each $n_i\text{,}$ we can do the entire sum modulo $n_i\text{.}$ The previous item shows

$\begin{equation*} x\equiv 0+0+\cdots +a_i +\cdots +0\text{ (mod }n_i)\text{.} \end{equation*}$

So the sum is definitely a simultaneous solution to all the congruences.

Finally, 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\text{.}$ 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\text{,}$ then $ab\mid c$ ). So $x'\equiv x$ (mod $N$ ), which means $x$ is the only solution modulo $N\text{!}$

🔗

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.

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

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
print(c_1,c_2,c_3)

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.

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

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.

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)
print(a_1*c_1*d_1, a_2*c_2*d_2,a_3*c_3*d_3)
print(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 that is because the solution is only unique modulo $N\text{:}$

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

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.

xxxxxxxxxx
 
a,b,c = 1,2,3
print(a)
print(a,b,c)

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

xxxxxxxxxx
 
@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']])
def _(a_1=(r'\(a_1\)',1), a_2=(r'\(a_2\)',2), a_3=(r'\(a_3\)',3), n_1=(r'\(n_1\)',5), n_2=(r'\(n_2\)',6), n_3=(r'\(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 = r"<ul><li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_1,n_1)
        string2 = r"<li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_2,n_2)
        string3 = r"<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 as e:
        pretty_print(html("Make sure the moduli are appropriate for solving!"))
        pretty_print(html("Sage gives the error message:"))
        pretty_print(html(e))

🔗

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.

🔗

Proposition 5.4.5. Converting to and from coprime moduli.

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

Certainly if $N$ divides $X-Y\text{,}$ so does a factor of $N\text{,}$ so $X\equiv Y$ (mod $m_i$ ) for each of the relatively prime factors of $N\text{.}$ 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*}$

🔗

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.