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

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

(2)Substituting this into the second congruence gives us:

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

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

(5)Substituting this into the second linear congruence yields:

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

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

(8)Substituting this into the second linear congruence gives us:

(9)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)Hence we can use $-1$ as our inverse. Thus:

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

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

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)Substituting this to the second congruence and we get that:

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

(16)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)Substituting this into our last linear congruence gives us:

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