# 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:**

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)We can now substitute this back into the second congruence to obtain:

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

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

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

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

(7)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:**

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)We can thus substitute this into our second congruence to obtain:

(10)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)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)Applying the inverse we get that:

(13)Hence:

(14)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)Hence $x = 224, 488$ are solutions modulo $528$.