Solving Systems of Linear Congruences 1

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 7 \pmod {38} \\ x & \equiv 79 \pmod {93} \end{align}

Since $(38, 93) = 1$, by the Chinese remainder theorem there will be a unique solution modulo $3534$.

Let's look at the first congruence, $x \equiv 7 \pmod {38}$ It thus follows that for some $k_1 \in \mathbb{Z}$ that:

(2)

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

We can now substitute this back into the second congruence to obtain:

(3)

\begin{align} 7 + 38k_1 & \equiv 79 \pmod {93} \\ 38k_1 & \equiv 72 \pmod {93} \end{align}

Now let's apply the division algorithm to find an inverse to $38$ modulo $93$:

(4)

\begin{align} 93 &= 38(2) + 17 \\ 38 &= 17(2) + 4 \\ 17 &= 4(4) + 1 \\ 4 &= 1(4) + 0 \\ \\ 1 &= 17 + 4(-4) \\ 1 &= 17 + [38 + 17(-2)](-4) \\ 1 &= 38(-4) + 17(9) \\ 1 &= 38(-4) + [93 + 38(-2)](9) \\ 1 &= 93(9) + 38(-22) \end{align}

Thus $-22$ works as an inverse for $38$ moduloe $93$. Let's apply this inverse to our congruence:

(5)

\begin{align} (-22) 38 k_1 & \equiv -22 (72) \pmod {93} \\ k_1 & \equiv -1584 \pmod {93} \\ k_1 & \equiv 90 \pmod {93} \end{align}

Thus it follows that for some $k_2 \in \mathbb{Z}$:

(6)

\begin{equation} k_1 = 90 + 93k_2 \end{equation}

Plugging this into our equation for $x$ and we get:

(7)

\begin{align} x &= 7 + 38(90 + 93k_2) \\ x &= 3427 + 3534k_2 \end{align}

So we have that $x \equiv 3427 pmod {3534}$. so $x = 3427$ is the unique solution to our linear congruences modulo $3534$.

Example 2

Solve the following system of linear congruences:

(8)

\begin{align} x & \equiv 4 \pmod {22} \\ x & \equiv 8 \pmod {24} \end{align}

We will solve this system in a similar manner. Since$x \equiv 4 \pmod {22}$ it follows that for some $k_1 \in \mathbb{Z}$ that:

(9)

\begin{align} \quad x = 4 + 22k_1 \end{align}

We can thus substitute this into our second congruence to obtain:

(10)

\begin{align} 4 + 22k_1 & \equiv 8 \pmod {24} \\ 22k_1 & \equiv 4 \pmod {24} \end{align}

We will apply an earlier prove theorem that states if $(a, m) = d$, and $d \mid b$, then there exists $d$ solutions. In this case $(22, 24) = 2$, and $2 | 4$, so there exists $2$ solutions to this linear congruence. Let's find them by finding an inverse for $22$ modulo $24$ by the division algorithm:

(11)

\begin{align} 24 &= 22(1) + 2 \\ 22 &= 2(11) + 0 \\ 2 &= 24(1) + 22(-1) \end{align}

It thus follows that -1 can be used as our inverse. Before we apply it, let's divide our linear congruence by $2$ to obtain:

(12)

\begin{align} 11k_1 \equiv 2 \pmod {12} \end{align}

Applying the inverse we get that:

(13)

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

Hence:

(14)

\begin{align} k_1 \equiv 10 \pmod {12} \end{align}

So there exists a $k_2 \in \mathbb{Z}$ such that $k_1 = 10 + 12k_2$. Substituting this into our equation for $x$ gives us:

(15)

\begin{align} x & = 4 + 22(10 + 12k_2) \\ x & = 224 + 264k_2 \end{align}

Hence $x = 224, 488$ are solutions modulo $528$.