5.5 Simultaneous linear congruences
In linear algebra, you learn how to solve simultaneous linear equations, for example \[ \begin{array}{lcrcr} 3x&+&4y&=&5\\ -9x&-&8y&=&7 \end{array} \] We now consider the solution of simultaneous congruences. In the first century A.D., the Chinese mathematician Sun-Tsu considered problems similar toIn other words, he wanted to find \(x\) such that the congruences \[x\equiv 2\text{ mod }(3)\,,\quad x\equiv 3\text{ mod }(5)\,,\quad x\equiv 2\text{ mod }(7)\] are simultaneously true. Such problems are thought to have been motivated by observing planetary conjunctions and eclipses.
What do the solutions look like?
Note that if \(x_0\) is any solution, then so is \(x_0+(3\times 5\times 7)t\) for any integer \(t\), so the solutions form a union of congruence classes \(\text{mod }(105)\).
What are the solutions to the simultaneous congruences \[x\equiv 3\text{ mod }(9)\,, x\equiv 2\text{ mod }(6)?\] The simultaneous congruences \(x\equiv 3\text{ mod }(9)\,, x\equiv 2\text{ mod }6\) have no solutions, since if \(x\equiv 3\text{ mod }(9)\) then \(3\) divides \(x\), whereas if \(x\equiv 2\text{ mod }(6)\) then \(3\) does not divide \(x\).
The Chinese Remainder Theorem
The following result, known as the Chinese Remainder Theorem, gives a very satisfactory solution to this type of problem.
Let \(n_1, n_2, \ldots, n_k\) be positive integers, with \(\gcd(n_i, n_j)=1\) whenever \(i\neq j\), and let \(a_1, a_2, \ldots, a_k\) be any integers. Then the solutions of the simultaneous congruences \[x\equiv a_1\text{ mod }(n_1)\,,\quad x\equiv a_2\text{ mod }(n_2)\,,\quad \ldots,\quad x\equiv a_k\text{ mod }(n_k)\] form a single congruence class \(\text{mod }(n)\), where \(n=n_1n_2\ldots n_k\).
An application to counting
Suppose we wish to count a large gathering of people, and we know there are around 80 of them. We can do so using the Chinese remainder theorem as follows:
- [Step 1] Get the people to self organize into groups of \(7\) and count the remainder, \(a_1\),
- [Step 2] Now get them to self organize into groups of \(13\) and count the remainder \(a_2\)
- [Step 3] If \(n\) is the number of people present we now know that \(n\equiv a_1\) mod \((7)\) and \(n\equiv a_2\) mod \(13\). Since \(7\) and \(13\) are coprime we can solve these simultaneous congruences to determine \(n\) mod \(7.13=91\). Since we know that \(n\) is around \(80\) this is enough to determine \(n\).
Of course, to carry out the exercise we need to know how to solve simultaneous congruences. The proof of Theorem 3.10 tells us how to do this.
Proof. Let \(c_in_i=n\), so \(c_i=n_1\ldots n_{i-1}n_{i+1}\ldots n_k\) for each \(i=1, \ldots, k\). Since each of its factors \(n_j\;(j\neq i)\) is coprime to \(n_i\), so is \(c_i\). Corollary 5.32 therefore implies that for each \(i\), the congruence \(c_ix\equiv 1\text{ mod }(n_i)\) has a single congruence class \([d_i]\) of solutions \(\text{mod }(n_i)\). We now claim that the integer \[x_0=a_1c_1d_1+a_2c_2d_2+ \cdots +a_kc_kd_k\] simultaneously satisfies the given congruences, that is, \(x_0\equiv a_i\text{ mod }(n_i)\) for each \(i\). To see this, note that each \(c_j\) (other than \(c_i\)) is divisible by \(n_i\), so \(a_jc_jd_j\equiv 0\text{ mod }n_i\) and hence \(x_0\equiv a_ic_id_i\text{ mod }(n_i)\). But \(c_id_i\equiv 1\text{ mod }n_i\) and so \(x_0\equiv a_i\text{ mod }n_i\) as required. Thus \(x_0\) is a solution of the simultaneous congruences, and it immediately follows that the entire congruence class \([x_0]\) of \(x_0\text{ mod }(n)\) consists of solutions.
To see that this class is unique, suppose that \(x\) is any solution. Then \(x\equiv a_i\equiv x_0\text{ mod }(n_i)\) for all \(i\) and so each \(n_i\) divides \(x-x_0\). Since \(n_1, \dots, n_k\) are mutually coprime, repeated use of Corollary 3.27(a) implies that their product \(n\) also divides \(x-x_0\), so \(x\equiv x_0\text{ mod }(n)\).
Comments
- The proof of Theorem 5.22, which we postponed until later, now follows immediately: given \(n=p_1^{e_1}\ldots p_k^{e_k}\), we put \(n_i=p_i^{e_i}\) for \(i=1, \ldots, k\), so \(n_1, \ldots, n_k\) are mutually coprime with product \(n\); the Chinese Remainder Theorem therefore implies that the solutions of the simultaneous congruences \(x\equiv b\text{ mod }(n_i)\) form a single congruence class \(\text{mod }(n)\); clearly \(b\) is a solution, so these congruences are equivalent to \(x\equiv b\text{ mod }(n)\).
- Note that the proof of the Chinese Remainder Theorem does not merely show that there is a solution for the simultaneous congruences; it also gives us a formula for a particular solution \(x_0\), and hence for the general solution \(x=x_0+nt\;(t\in{\mathbb Z})\). We shall see shortly that there is often an easier method to compute the solution.
Consider our original problem \[x\equiv 2\text{ mod }(3)\,,\quad x\equiv 3\text{ mod }(5)\,,\quad x\equiv 2\text{ mod }(7)\,,\]
Solution. We have \(n_1=3, n_2=5\) and \(n_3=7\), so \(n=105, c_1=35, c_2=21\) and \(c_3=15\). We first need to find a solution \(x=d_1\) of \(c_1x\equiv 1\text{ mod }(n_1)\), that is, \(35x\equiv 1\text{ mod }(3)\); this is equivalent to \(-x\equiv 1\text{ mod }(3)\), so we can take \(x=d_1=-1\) for example.
Similarly, \(c_2x\equiv 1\text{ mod }(n_2)\) gives \(21x\equiv 1\text{ mod }(5)\), that is, \(x\equiv 1\text{ mod }(5)\), so we can take \(x=d_2=1\), while \(c_3x\equiv 1\text{ mod }(n_3)\) gives \(15x\equiv 1\text{ mod }(7)\), that is, \(x\equiv 1\text{ mod }(7)\), so we can also take \(x=d_3=1\).
Of course, different choices of \(d_i\) are possible here, leading to different values of \(x_0\), but they will all give the same congruence class of solutions \(\text{mod }(105)\).
We now have \[x_0=a_1c_1d_1+a_2c_2d_2+a_3c_3d_3 =2.35.(-1)+3.21.1+2.15.1=23\,,\] so the solutions form the congruence class \([23]\text{ mod }(105)\), that is, the general solution is \(x=23+105t\;(t\in{\mathbb Z})\).
We can also use the Chinese Remainder Theorem as the basis for a second method for solving simultaneous linear congruences, which is often more efficient.
We start by finding a solution \(x=x_1\) to one of the congruences - usually it is best to start with the congruence involving the largest modulus, for reasons that should become apparent. We illustrate by considering the congruences in Example 5.41. Starting with \(x\equiv 2\text{ mod }(7)\), which has \(x_1=2\) as an obvious solution, and so the ‘general solution’ for this congruence is \[ x = 2 + 7t, t\in\mathbb Z. \]
Notice that there is no real work involved at this point. We want this general solution to also satisfy the other congruences, so taking the next highest modulus we require \[ 2+7t\equiv 3\text{ mod }(5), \] or equivalently \(7t\equiv1\text{ mod }(5)\). We solve this using our 4-point algorithm as in previous examples: Since \(7\equiv2\text{ mod }(5)\) we can simplify to \[ 2t\equiv1\equiv6\text{ mod }(5) \] and so \(t\equiv3\text{ mod }(5)\). Hence \(t = 3 + 5s\) for \(s\in\mathbb Z\) and so \(x = 2+7t = 2+7(3+5s) = 23+35s\) for \(s\in\mathbb Z\). This is then the general solution for the simultaneous congruences \[ x\equiv 3\text{ mod }(5)\,,\quad x\equiv 2\text{ mod }(7)\,. \]
Notice how starting with the modulus with the highest value, reduces the coefficient in front of \(t\) immediately, and makes for an easier solution.
We now want this solution to satisfy our final congruence \(x\equiv2\text{ mod }(3)\) and so we solve \[ 23+35s\equiv2\text{ mod }(3). \] Since \(23\equiv2\text{ mod }(3)\) and \(35\equiv2\text{ mod }(3)\) then we have \[ 2s\equiv0\text{ mod }(3) \] which has a solution of \(s\equiv0\text{ mod }(3)\) or \(s = 3r\) for \(r\in\mathbb Z\). Hence \(x = 23 + 35(3r) = 23 + 105r\) for \(r\in\mathbb Z\) is the general solution to all three congruences. Notice that this method only involves solving 2 congruences, whereas the method in the proof of Theorem 5.40 involves solving three (to find the values \(d_1, d_2\) and \(d_3\)).
Solve the simultaneous congruences \[x\equiv 1\text{ mod }(4),\quad x\equiv 2\text{ mod }(3),\quad x\equiv 3\text{ mod }(5)\,.\]
Solve the simultaneous congruences \[x\equiv 2\text{ mod }(7),\quad x\equiv 7\text{ mod }(9),\quad x\equiv 3\text{ mod }(4)\,.\]
Generalising the CRT
The linear congruences in the Chinese Remainder Theorem are all of the form \(x\equiv a_i\) mod \((n_i)\). If we are given a set of simultaneous linear congruences, with one (or more) of them in the more general form \(ax\equiv b\text{ mod }(n_i)\), then we will first need to use the earlier algorithm to solve this congruence, expressing its general solution as a congruence class modulo some divisor of \(n_i\); it will then be possible to apply the techniques based on the Chinese Remainder Theorem to solve the resulting simultaneous congruences.
Consider the simultaneous congruences \[7x\equiv 3\text{ mod }(12),\quad 10x\equiv 6\text{ mod }(14)\,.\]
Solution. We saw in Examples 11 and 12 that the first of these congruences has the general solution \(x=9+12t\), and that the second has the general solution \(x=2+7t\).
It follows that we can replace the original pair of congruences with the pair \[x\equiv 9\text{ mod }(12),\quad x\equiv 2\text{ mod }(7)\,.\]
Clearly, \(x_0=9\) is a particular solution; since the moduli \(12\) and \(7\) are coprime, with product \(84\), the Chinese Remainder Theorem implies that the general solution has the form \(9+84t\).
Solve the simultaneous congruences \[3x\equiv 6\text{ mod }(12),\quad 2x\equiv 5\text{ mod }(7),\quad 3x\equiv 1\text{ mod }(5)\,.\]
Simplifying congruences
The Chinese Remainder Theorem can be used to convert a single congruence, with a large modulus, into several simultaneous congruences with smaller moduli, which may be easier to solve.
Consider the linear congruence \[13x\equiv 71\text{ mod }(380)\,.\]
Solution. Instead of using the algorithm described earlier for solving a single linear congruence, we can use the factorisation \(380=2^2\times 5\times 19\), together with Theorem 5.22, to replace this congruence with the three simultaneous congruences \[13x\equiv 71\text{ mod }(4)\,,\quad 13x\equiv 71\text{ mod }(5)\,,\quad 13x\equiv 71\text{ mod }(19)\,.\]
These immediately reduce to
\[x\equiv 3\text{ mod }(4)\,,\quad 3x\equiv 1\text{ mod }(5)\,,\quad 13x\equiv 14\text{ mod }(19)\,.\]
The first of these needs no further simplification, but we can apply the single congruence algorithm to simplify each of the other two.
We write the second congruence as \(3x\equiv 6\text{ mod }(5)\), so dividing by \(3\) (which is coprime to \(5\)) we get \(x\equiv 2\text{ mod }(5)\).
Similarly, the third congruence can be written as \(-6x\equiv 14\text{ mod }(19)\), so dividing by \(-2\) we get \(3x\equiv -7\equiv 12\text{ mod }(19)\), and now dividing by \(3\) we have \(x\equiv 4 \text{ mod }(19)\).
Our original congruence is therefore equivalent to the simultaneous congruences \[x\equiv 3\text{ mod }(4)\,,\quad x\equiv 2\text{ mod }(5)\,,\quad x\equiv 4\text{ mod }(19)\,.\] Now these have mutually coprime moduli, so the Chinese Remainder Theorem applies, and we can use either of our two methods to find the general solution.
Using the second method, we start with a solution \(x_1=4\) of the third congruence; adding and subtracting multiples of \(19\), we find that \(x_2=42\) also satisfies the second congruence, and then adding and subtracting multiples of \(19\times 5=95\) we find that \(327\) (or equivalently \(-53\)) also satisfies the first congruence. Thus the general solution has the form \(x=327+380t\;(t\in{\mathbb Z})\).
Solve the congruence \(91x\equiv 419\text{ mod }(440)\).