What happens if, in a system of congruences, we don't have the enviable situation where all the \(n_i\) are relatively prime? Let's go back to the interact from before one last time, with some moduli which are not pairwise coprime, and see if we get anything.

As previously mentioned, Qin discovered a very general answer for getting answers in this situation. An answer exists as long as \(\gcd(n_i,n_j)\) divides \(a_i-a_j\) for all \(i\) and \(j\). Lebèsgue was the first to rediscover this in the modern era, in 1859.

Another case is that of 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 when our linear system has coefficients to the variable?

If you have simultaneous congruences with coefficients, \begin{equation*}A_ix\equiv B_i\text{ (mod }N_i)\end{equation*} 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, try now to solve

• \(2x\equiv 2\) (mod \(5\))

• \(5x\equiv 4\) (mod \(6\))

• \(3x\equiv 2\) (mod \(7\))

Surprised? Don't forget to get back to the original modulus!

See also Example 6.5.2 for combining these ideas with those of Proposition 5.4.2.

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 one can use the CRT, in particular the ideas of Proposition 5.4.2.

• First, pick a few mutually coprime moduli smaller than the biggest you can add on your computer.

• Then, reduce your two numbers \(x\) and \(y\) modulo those moduli and add the two huge numbers in each of those moduli.

• Then the CRT allows you to put \(x+y\) modulo each of the moduli back together for a complete solution!

Needless to say, we won't do an actual example of this.