Example 5.5.1.
For instance, try now to solve this system:
- \(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!
Section 5.5 More Complicated Cases
Solving linear congruences is a completely solved problem (up to computer power). Although one does not usually cover all extensions in an introductory course, the following subsections will introduce some, without full detail.
Subsection 5.5.1 Moduli which are not coprime
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 method for getting answers in this situation. From his method, he seems to have been aware that an answer exists as long as \(\gcd(n_i,n_j)\) divides \(a_i-a_j\) for all \(i\) and \(j\text{,}\) though he did not explicitly state (and certainly did not prove) it. V.-A. Lebèsgue 4 was the first to rediscover this latter fact in the modern era, in 1859. (See [E.7.44] for a comparative analysis with some Indian and European developments.)
Subsection 5.5.2 The case of coefficients
Another case is that of congruences not of the form \(x \equiv a\text{ (mod }n)\text{,}\) but of the form \(Ax\equiv B\text{ (mod }n)\text{.}\) What can we say when there are coefficients for the variable in our linear system?
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.
See also Example 6.5.2 for combining these ideas with those of Proposition 5.4.5.
Subsection 5.5.3 A practical application
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.5.
- 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. See [E.2.4, Chapter 3.3] for a basic example and a reference.
www-history.mcs.st-andrews.ac.uk/Biographies/Lebesgue_Victor.html
