# Additional Examples of Solving Systems of Linear Congruences

## Example 1

**Solve the following system of linear congruences:**

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 k_{1}. Substituting this to the second congruence we get that:

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)Hence $k_1 = 4 + 12k_2$ for some k_{2}. 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:

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)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.