| | |
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 $$x = 3A + 5B + 7C$$
is a solution to our system of congruences. Note:
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& (11 \cdot 13)^{-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.
As such, 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 $$x = 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}$$