Solving a System of Congruences Simultaneously

Suppose we wish to solve the following system of congruences: $$\begin{array}{rcl} x &\equiv& 3\pmod{11}\\ x &\equiv& 5\pmod{13}\\ x &\equiv& 7\pmod{19}\\ \end{array}$$ One interesting way to proceed starts by trying to find integers $A$, $B$, and $C$ so that $$N = 3A + 5B + 7C$$

Note:

  • If $A \equiv 1\pmod{11}$, the first congruence requires $B$ and $C$ to both be multiples of $11$.
  • If $B \equiv 1\pmod{13}$, the second congruence requires both $A$ and $C$ to be a multiples of $13$.
  • If $C \equiv 1\pmod{19}$, the third congruence requires both $A$ and $B$ must both be multiples of $19$.

As such, let $n_{11}, n_{13}$ and $n_{19}$ be chosen so that $$\begin{array}{rcl} n_{11} &\equiv& (13 \cdot 19)^{-1}\pmod{11}\\ n_{13} &\equiv& (11 \cdot 19)^{-1}\pmod{13}\\ n_{19} &\equiv& (13 \cdot 19)^{-1}\pmod{19} \end{array}$$ and then take $$\begin{array}{rcl} A &=& 13 \cdot 19 \cdot n_{11}\\ B &=& 11 \cdot 19 \cdot n_{13}\\ C &=& 11 \cdot 13 \cdot n_{19} \end{array}$$

In this way, all three of the given congruences will hold.

All that remains is to find the smallest positive $x$ so that $$x \equiv N\pmod{11 \cdot 13 \cdot 19}$$

So, finishing the example started above, we note that $$\begin{array}{rcllll} 13 \cdot 19 &\equiv& 247 &\equiv& 5&\pmod{11}\\ 11 \cdot 19 &\equiv& 209 &\equiv& 1&\pmod{13}\\ 11 \cdot 13 &\equiv& 143 &\equiv& 10&\pmod{19} \end{array}$$ and calculate (using the Euclidean Algorithm, or some other means): $$\begin{array}{rcl} 5^{-1} \equiv 9\pmod{11}\\ 1^{-1} \equiv 1\pmod{13}\\ 10^{-1} \equiv 2\pmod{19} \end{array}$$ Using $n_{11} = 9, n_{13} = 1$, and $n_{19} = 2$, we find $$N = 3(13 \cdot 19 \cdot 9) + 5(11 \cdot 19 \cdot 1) + 7(11 \cdot 13 \cdot 2) = 9716$$ and finally, $$x = 9716 \textrm{ mod } (11 \cdot 13 \cdot 19) = 9716 \textrm{ mod } 2717 = 1565$$

Sure enough, we can quickly verify $$\begin{array}{rcl} 1565 &\equiv& 3\pmod{11}\\ 1565 &\equiv& 5\pmod{13}\\ 1565 &\equiv& 7\pmod{19}\\ \end{array}$$

◆ ◆ ◆