Solving a system of Congruences
If you divide \(x\) by \(5\) you obtain a remainder of \(2\). Divide it by \(3\) you obtain a remainder of \(1\). Divide it by \(7\) you obtain a remainder of \(4\). What is the general solution?
Motivation
Suppose we want to solve the system:
\[\begin{aligned} & x \equiv a_1 \space (\text{mod} \space n_1) \\ & x \equiv a_2 \space (\text{mod} \space n_2) \end{aligned}\]where \(n_1\) and \(n_2\) are coprime.
It can be easily verified that a solution is given by:
\[x=a_1 m_2 n_2+a_2 m_1 n_1,\]where \(m_1\) and \(m_2\) are from Bézout’s identity:
\[m_1 n_1+m_2 n_2=1\]Example
Given the system of congruences:
\[\begin{aligned} & x \equiv 2 \space (\text{mod} \space 5) \\ & x \equiv 1 \space (\text{mod} \space 3) \end{aligned}\]Using the Bezout’s identity, we can find the coefficients of the linear combination of the moduli that equal \(1\). In this case, we have:
\[5(5) - 8(3) = 1\]Now, let’s find a solution using the coefficients obtained from the Bezout’s identity. We can substitute these coefficients into the system of congruences:
\[\begin{align*} x &= 2(3)(-8) + 1(5)(5) \\ x &= -48 + 25 \\ x &= -23 \end{align*}\]Now, notice that the first system has a “cycle” of \(5\) (since it is mod \(5\)), whereas the second system has a “cycle” of \(3\). To satisfy both, we need to have a “cycle” of \(15\).
Therefore our solution can be written as:
\[x \equiv -23 \space (\text{mod} \space 15)\]Or simply:
\[x \equiv 7 \space (\text{mod} \space 15)\]General Case
This process can be generalized using an inductive approach:
Example
Consider:
\[\begin{aligned} & x \equiv 2 \space (\text{mod} \space 5) \\ & x \equiv 1 \space (\text{mod} \space 3) \\ & x \equiv 4 \space (\text{mod} \space 7) \end{aligned}\]From our solution above, we can simplify it into:
\[\begin{aligned} & x \equiv 7 \space (\text{mod} \space 15) \\ & x \equiv 4 \space (\text{mod} \space 7) \end{aligned}\]Now consider:
\[1(15) - 2(7) = 1\]As \(x=a_1 m_2 n_2+a_2 m_1 n_1\),
\[\begin{align*} x &= 4(15)(1) + 7(7)(-2) \\ x &= 60-98 \\ x &= -38 \end{align*}\]Hence, the solution is:
\[x \equiv -38 \space (\text{mod} \space 105)\]Or simply:
\[x \equiv 67 \space (\text{mod} \space 105)\]Conclusion
Any reader with experience in Number Theory will realize this is simpliy an example of the famous Chinese Remainder Theorem. It is applications in various applications in number theory, modular arithmetic, and cryptography.
