Section6.4Using the Chinese Remainder Theorem
We will here present a completely constructive proof of the CRT. 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.
Subsection6.4.1Constructing simultaneous solutions
Remember that we are trying to solve the system of equations \(x\equiv a_i\) mod (\(n_i\)). (Remember that all \(n_i\) are coprime in pairs.) Here are the steps we'll take.
- 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, find \(d_i\) such that \[c_i d_i\equiv 1\text{ mod (}n_i)\text{ for all }i\; .\]
- Notice that this is possible. You can't find an inverse modulo any old thing! But in this case, \(c_i\) was constructed to be a product of a bunch of numbers, all of which are coprime to \(n_i\). So we are okay.
- For each \(i\), multiply the three numbers \(a_i \cdot c_i \cdot d_i\).
- Here is a harder step - evaluating each of those products modulo the various \(n_j\).
- By definition, each \(c_j\) is divisible by \(n_i\) (except for \(c_i\) itself), so modulo \(n_i\) the product is \[a_j c_j d_j \equiv 0\text{ mod }(n_i)\; .\]
- The product \[a_i c_i d_i \equiv a_i \cdot 1\equiv a_i\text{ mod }(n_i)\; ,\] of course.
- Now add all these numbers together to get \[x=a_1 c_1 d_1+a_2 c_2 d_2+\cdots +a_k c_k d_k\; .\] For each \(n_i\), we can do the sum modulo \(n_i\) too; the previous step shows this sum is \[x\equiv 0+0+\cdots +a_i +\cdots +0\text{ mod }(n_i)\; .\]
- 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|c\) and \(b|c\) and \(gcd(a,b)=1\), then \(ab|c\)). So \(x'\equiv x\) mod (\(N\)) - which means \(x\) is the only solution modulo \(N\)!
Clearly this needs an example.
Example6.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)
First, I'll make sure I know all my initial constants.
Next, I'll write down all the \(c_i\), the complements to the moduli, so to speak. Remember, \(c_i=N/n_i\).
Now we need to solve for the inverse of each \(c_i\) modulo \(n_i\). One could do this by hand. For instance, \[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)\; .\] But that is best done on homework for careful practice; in the text, we might as well use the power of Sage.
Now I'll create each of the big product numbers, as well as their sum.
Of course, we don't recognize 836 as our answer. But:
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)
Subsection6.4.2Using the CRT
Now, there are many, many useful things we can do with the CRT. First, a theoretical - but highly important one.
Proposition6.4.2Converting to and from prime powers
Suppose that \(X\equiv Y\) mod (\(N\)), and \(N=\prod p_i^{e_i}\). 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 \((p_i^{e_i})\) for each prime power factor 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. After all, all the powers of primes in a prime factorization are coprime to each other, so the simultaneous solution of the system \[X\equiv Y\text{ mod }(p_i^{e_i}) \] will give one (!) solution of \[X\equiv Y\text{ mod (N)}\]
That means that any question about congruences is really a question about congruences modulo prime powers. We will use this fact again and again in the remainder of the text, and it is a huge reason why the CRT is so intensely powerful.
Let's solve \[x\equiv 31 \text{ mod }180\] this way.
- What are the individual congruences?
- Can we then put them back together?
Another practical idea would be about congruences not of the form \(x \equiv a\text{ mod }(n)\), but of the form \(Ax\equiv B\text{ mod }(n)\). What can we say here?
- If you have several simultaneous congruences \(A_ix\equiv B_i\) mod (\(N_i\)), then first write their individual solutions in the form \(x\equiv a_i\) mod (\(n_i\)). Then you can use the CRT to get a solution of that system, which is also a solution of the 'big' system.
- For instance, solve
- \(2x\equiv 2\) mod (5)
- \(5x\equiv 4\) mod (6)
- \(3x\equiv 2\) mod (7)
Surprised?
- Similarly, if you have one complicated congruence \(Ax\equiv B\) mod (\(N\)) with a composite modulus \(N\), you can just take \(N=p_1^{e_1}\cdots p_k^{e_k}\) and then solve all the congruences \(Ax\equiv B\) mod (\(p_i^{e_i}\)) first. Then use the CRT to 'patch' them together for a final solution. This is a little tedious, but certainly doable.
- Try solving this: \[21x\equiv 31 \text{ mod }180\]
- Don't forget in both cases to get back to the original modulus!
Finally, there is a practical application. Suppose you are adding two very large numbers - too big for your computer! How would you do it?
- The answer is using the CRT.
- You pick a few mutually coprime moduli smaller than the biggest you can add.
- Then you reduce your two numbers \(x\) and \(y\) modulo those moduli.
- Then you add your two huge numbers in each of those moduli.
- Then the CRT helps you put \(x+y\) modulo each of the moduli back together!
- But we won't do such an example.
