In this lesson we will show how to solve a systems of linear congruences with one unknown, that is, systems of the shape
$$a_1 x \equiv b_1 \pmod{m_1}.$$
$$a_2 x \equiv b_2 \pmod{m_2}.$$
The idea is simple. Solve first one of them and then find its solutions that also satisfy the another.
Example 1. Solve the following system of linear congruences:
$$5x \equiv 8 \pmod 2,$$
$$7x \equiv 3 \pmod 5.$$
Solution.
Firstly, we will determine a solution to the congruence $7x \equiv 3 \pmod 5$. Since $\gcd (7, 5) =1$, that the congruence has a unique solution.
The congruence we write in the equivalent way:
$$7x – 5y = 3.$$
The one particular solution to the equation above is $x_0 = 2, y_0 = -3$, so $7x_0 – 5y_0 = 3$ is valid. By subtracting the obtained equations we obtain
$$7(x – x_0) – 5 (y – y_0) = 0.$$
It follows
$$x – x_0 = 5t_1, \quad k_1 \in \mathbb{Z},$$
that is,
$$ x = 2 + 5k_1, \quad k_1 \in \mathbb{Z}.$$
Substituting that into the first congruence gives:
$$5 ( 2 + 5k_1) \equiv 8 \pmod 2,$$
that is,
$$25 k_1 \equiv 2 \pmod 2.$$
The associated linear Diophantine equation of the congruence above is:
$$25 k_1 – 2 y = 2.$$
One particular solution to the equation above is $k_1^0 = 2, y_0 = 24$, so
$$k_1 = 2 + 2k_2, \quad k_2 \in \mathbb{Z}.$$
If we substituting that into $x = 2 + 5k_1$, then we obtain
$$x = 2 + 5 (2 + 2k_2) = 12 + 10 k_2,$$
that is,
$$x \equiv 2 \pmod{10},$$
and that is the solution to the given system of linear congruences.
If we need to solve a system of three linear congruences with one unknown, then we need first solve a system of two linear congruences, and then see which of the obtained solutions also satisfy the third congruence. With the increase in the number of congruences, the process becomes more complicated. That help us the following theorem.
Theorem (the Chinese remainder theorem) Let $m_1, m_2, \ldots, m_r$ be nonzero integers that are pairwise relatively prime. Then, for any integers $a_1, a_2, \ldots, a_r$, the system of congruences
$$x \equiv a_1 \pmod{m_1}$$
$$x \equiv a_2 \pmod{m_2}$$
$$\vdots$$
$$x \equiv a_r \pmod{m_r}$$
has a solution. If $x_0$ is the one solution, then all solutions are given by
$$x \equiv x_0 \pmod{m_1m_2 \cdots m_r}.$$
A proof of the Chinese remainder theorem gives us an algorithm for solving a system of linear congruences with one unknown.
Proof.
Put $M= m_1m_2 \cdots m_r$, and $M_j =\frac{M}{m_j}$, for $j=1, \ldots, r$.
Then $\gcd(M_j, m_j) = 1$. Let $y_j$ be an inverse of $M_j$ modulo $m_j$. Then we have
$$M_jy_j \equiv 1 \pmod{m_j},$$
by the definition of the inverse.
Let now
$$x =a_1 M_1x_1 + a_2M_2x_2 + \ldots + a_rM_rx_r.$$
Then $x$ is a simultaneous solution to the given system of linear congruences.
If now $x$ and $y$ are two simultaneous solutions to the given system, then $x \equiv y \pmod{m_j}$ for $j= 1, \ldots, r$, so because $m_j$ are pairwise relatively prime , we obtain that $x \equiv y \pmod M$, that is, the solution is a unique congruence class modulo $M$, and the value of $x$ computed above is in that class.
Systems that have no solution are said to be inconsistent.
Example 2. Solve the following system of congruences:
$$x \equiv 2 \pmod 3$$
$$x \equiv 3 \pmod 5$$
$$x \equiv 2 \pmod 7.$$
Solution.
Notice first that the moduli are pairwise relatively prime, therefore, we can use the Chinese remainder theorem. In the notation of the Chinese remainder theorem, we have:
$$m_1 = 3, \quad m_2 = 5, \quad m_3 = 7,$$
so,
$$M = m_1 m_2 m_3 = 3 \cdot 5 \cdot 7 = 105,$$
and
$$M_1 = \frac{M}{m_1} = \frac{105}{3} = 35,$$
$$M_2 = \frac{M}{m_2} = \frac{105}{5} = 21,$$
$$M_3 = \frac{M}{m_3} = \frac{105}{7} = 15.$$
Now the linear congruences
$$M_1 y_1 \equiv 1 \pmod 3 \Longrightarrow 35 y_1 \equiv 1 \pmod 3$$
$$M_2 y_2 \equiv 1 \pmod 5 \Longrightarrow 21 y_2 \equiv 1 \pmod 5,$$
and
$$M_3 y_3 \equiv 1 \pmod 7 \Longrightarrow 15 y_3 \equiv 1 \pmod 7$$
are satisfied by $y_1 = -1$, $y_2 = 1$ and $y_3 = 1$, respectively.
Thus, a solution to the given system is given by
$$x = ( 2 \cdot 35 \cdot (-1)) + (3 \cdot 21 \cdot 1 ) + (2 \cdot 15 \cdot 1)$$
$$= -70 + 63 + 30$$
$$= 23$$
modulo $105$. So the solutions form the congruence class of $23$ modulo $105$, that is, the general solution is
$$x = 23 + 105 k, \quad k \in \mathbb{Z}.$$
What if moduli are not pairwise relatively prime? The Chinese remainder theorem does not work in this case. If we have a congruence with a modulus which is divisible by at least two primes, then we can split this single congruence into several congruences as long as the new moduli are pairwise relatively prime and their product is the original modulus. After this procedure, we can use the Chinese remainder theorem.
Example 3. Solve the following system of congruences:
$$x \equiv 3 \pmod{10},$$
$$x \equiv 8 \pmod{15},$$
$$x \equiv 5 \pmod{84}.$$
Solution.
The moduli in this problem are not pairwise relatively prime, so we can not apply the Chinese remainder theorem directly, and it is possible that such a system has no solution.
Since $10 = 2 \cdot 5$, $15 = 3 \cdot 5$ and $84 = 2 \cdot 2 \cdot 3 \cdot 7$, the first congruence is equivalent to
$$x \equiv 3 \pmod 2, x \equiv 3 \pmod 5,$$
the second congruence is equivalent to
$$x \equiv 2 \pmod 3 , x \equiv 3 \pmod 5,$$
and the third congruence is equivalent to
$$x \equiv 5 \pmod 4 \quad, x \equiv 5 \pmod 3 \quad, x \equiv 5 \pmod 7.$$
Therefore, the original system is equivalent to the following system:
$$x \equiv 1 \pmod 4,$$
$$x \equiv 2 \pmod 3,$$
$$x \equiv 3 \pmod 5,$$
$$x \equiv 5 \pmod 7.$$
Now we can apply the method of the proof of the Chinese remainder theorem.
We have $m_1 = 4, m_2 = 3, m_3 = 5$ and $m_4 = 7$, therefore
$$M = 4 \cdot 3 \cdot 5 \cdot 7 = 420.$$
It follows
$$M_1 = \frac{M}{m_1} = \frac{420}{4} = 105,$$
$$M_2 = \frac{M}{m_2} = \frac{420}{3} = 140,$$
$$M_3 = \frac{M}{m_3} = \frac{420}{5} = 84,$$
$$M_4 = \frac{M}{m_4} = \frac{420}{7} = 60.$$
Now the linear congruences
$$105 y_1 \equiv 1 \pmod 4,$$
$$140 y_2 \equiv 1 \pmod 3,$$
$$84y_3 \equiv 1 \pmod 5$$
and
$$60 y_4 \equiv 1 \pmod 7$$
are satisfied by $y_1 = 1, y_2 = 2, y_3= -1$ and $y_4 = 2$, respectively.
Thus, a solution to the given system is given by
$$x= (1 \cdot 105 \cdot 1) + (2 \cdot 140 \cdot 2) + (3 \cdot 84 \cdot (-1)) + (5 \cdot 60 \cdot 2)$$
$$= 1013$$
$$\equiv 173 \pmod{420}.$$
