Solving Systems of Linear Congruences 2

We will now begin to solve some systems of linear congruences. We will mention the use of The Chinese Remainder Theorem when applicable.

Example 1

Solve the following system of linear congruences:

(1)

\begin{align} x & \equiv 1 \pmod 6 \\ x & \equiv 17 \pmod {39} \end{align}

Since $x \equiv 1 \pmod 6$ we have that for some $k_1 \in \mathbb{Z}$ that:

(2)

\begin{align} \quad x = 1 + 6k_1 \end{align}

Substituting this into the second congruence gives us:

(3)

\begin{align} 1 + 6k_1 & \equiv 17 \pmod {39} \\ 6k_1 & \equiv 16 \pmod {39} \end{align}

Notice that that will only be solutions if when $(a, m) = d$ we have that $d \mid b$. But $(6, 39) = 3$ and $3 \not \mid 16$. So there exists no solutions to this system of linear congruences.

Example 2

Solve the following system of linear congruences:

(4)

\begin{align} x & \equiv 8 \pmod {12} \\ x & \equiv 6 \pmod {9} \end{align}

From the first congruence we have that there exists a $k_1 \in \mathbb{Z}$ such that:

(5)

\begin{align} \quad x = 8 + 12k_1 \end{align}

Substituting this into the second linear congruence yields:

(6)

\begin{align} 8 + 12k_1 & \equiv 6 \pmod 9 \\ 12k_1 & \equiv -2 \pmod 9 \\ 12k_1 & \equiv 7 \pmod 9 \end{align}

Since $(12, 9) = 3$ and $3 \not \mid 7$, this system of linear congruences has no solutions.

Example 3

Solve the following system of linear congruences:

(7)

\begin{align} x & \equiv 8 \pmod {12} \\ x & \equiv 6 \pmod {13} \end{align}

From the first linear congruence there exists a $k_1 \in \mathbb{Z}$ such that:

(8)

\begin{align} \quad x = 8 + 12k_1 \end{align}

Substituting this into the second linear congruence gives us:

(9)

\begin{align} 8 + 12k_1 & \equiv 6 \pmod {13} \\ 12k_1 & \equiv -2 \pmod {13} \\ 12k_1 & \equiv 11 \pmod {13} \end{align}

Notice that $(12, 13) = 1$, and $1 \mid 11$ so there exists a solution. Let's use the division algorithm to find the inverse of $12$ modulo $13$:

(10)

\begin{align} 13 & = 12(1) + 1 \\ 12 & = 1(12) + 0 \\ \\ 1 & = 13 + 12(-1) \end{align}

Hence we can use $-1$ as our inverse. Thus:

(11)

\begin{align} (-1)12k_1 & \equiv (-1)11 \pmod {13} \\ k_1 & \equiv -11 \pmod {13} \\ k_1 & \equiv 2 \pmod {13} \end{align}

Hence for some $k_2 \in \mathbb{Z}$, $k_1 = 2 + 13k_2$. Substituting this into our equation for $x$ yields:

(12)

\begin{align} x & = 8 +12(2 + 13k_2) \\ x & = 32 + 156k_2 \end{align}

Thus it follows that $x \equiv 32 \pmod {156}$, so $x = 32$ is the solution to this linear congruence.

Example 4

Solve the following system of linear congruences:

(13)

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

From the first linear congruence, for some $k_1 \in \mathbb{Z}$ we have that:

(14)

\begin{equation} x = 3 + 7k_1 \end{equation}

Substituting this to the second congruence and we get that:

(15)

\begin{align} 3 + 7k_1 & \equiv 7 \pmod {12} \\ 7k_1 & \equiv 4 \pmod {12} \end{align}

By inspection we can see that $7$ can be used as an inverse to $7$ modulo $12$ and thus:

(16)

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

So for some $k_2 \in \mathbb{Z}$ we have $k_1 = 4 + 12k_2$. We can substitute this back into our equation for x to get that:

(17)

\begin{equation} x = 3 + 7(4 + 12k_2) = 31 + 84k_2 \end{equation}

Substituting this into our last linear congruence gives us:

(18)

\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 an inverse of $16$ modulo $17$ which we will once again obtain by inspection. We note that $16$ will work. Hence:

(19)

\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 $x = 871$ which satisfies all three congruences.