Additional Examples of Solving Systems Of Linear Congruences

Additional Examples of Solving Systems of Linear Congruences

Example 1

Solve the following system of linear congruences:

(1)
\begin{align} x \equiv 3 \pmod 7 \\ x \equiv 7 \pmod {12} \\ x \equiv 4 \pmod {17} \end{align}

Since all of the moduli are relatively prime, we know that by the Chinese Remainder Theorem that this system of linear congruences has a solution modulo the product of the moduli.

First, we know that $x = 3 + 7k_1$ for some k1. Substituting this to the second congruence we get that:

(2)
\begin{align} 3 + 7k_1 \equiv 7 \pmod {12} \\ 7k_1 \equiv 4 \pmod {12} \end{align}

We now need to find a modular inverse of 7 (mod 12). We could use the division algorithm, but since 12 is relatively small, by inspection we can see that 7 can be used as a modular inverse. Hence it follows that:

(3)
\begin{align} (7)7k_1 \equiv (7)4 \pmod {12} \\ k_1 \equiv 28 \pmod {12} \\ k_1 \equiv 4 \pmod {12} \end{align}

Hence $k_1 = 4 + 12k_2$ for some k2. We can substitute this back into our equation for x to get that $x = 3 + 7(4 + 12k_2) = 31 + 84k_2$. Now we can substitute this back into our last congruence to get that:

(4)
\begin{align} 31 + 84k_2 \equiv 4 \pmod {17} \\ 14 + 16k_2 \equiv 4 \pmod {17} \\ 16k_2 \equiv -10 \pmod {17} \\ 16k_2 \equiv 7 \pmod {17} \end{align}

Hence we must find a modular inverse of 16 (mod 17), which we will once again obtain by inspection. We note that 16 will work. Hence it follows that:

(5)
\begin{align} (16)16k_2 \equiv (16)7 \pmod {17} \\ k_2 \equiv 112 \pmod {17} \\ k_2 \equiv 10 \pmod {17} \end{align}

When we substitute this back into our equation for x to get that $x = 31 + 84(10 + 17k_2) = 871 + 1428k_2$. Hence it follows that $x \equiv 871 \pmod {1428}$. Our solution is thus 871, which satisfies all three congruences.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License