# Additional Examples of Solving Linear Congruences

Recall the following properties regarding linear congruences:

**1)**If $ac \equiv bc \pmod m$ and $(c, m) = 1$, then $a \equiv b \pmod m$.

**2)**If $ac \equiv bc \pmod m$ and $(c, m) = d$, then $a \equiv b \pmod {m/d}$.

**3)**"*Solutions*" to linear congruences are regarded as least residues.

**4)**The linear congruence $ax \equiv b \pmod m$ has no solutions if $(a, m) \nmid b$.

**5)**The linear congruence $ax \equiv b \pmod m$ has 1 solution if $(a, m) = 1$.

**6)**The linear congruence $ax \equiv b \pmod m$ has b solutions if $(a, m) \mid b$.

We will apply these properties in solving the following linear congruences. More examples of solving linear congruences can be found here.

## Example 1

**Find all solutions to the linear congruence $5x \equiv 12 \pmod {23}$.**

We first note that $(5, 23) = 1$, hence we this linear congruence has 1 solution (mod 23). We can calculate this using the division algorithm.

(1)Hence -9 can be used as an inverse to our linear congruence $5x \equiv 12 \pmod {23}$. Thus:

(2)Hence our solution in least residue is 7 (mod 23).

## Example 2

**Find all solutions to the linear congruence $210x \equiv 40 \pmod {212}$.**

Let's first reduce this congruence. By property **2)**, we can see that we can take 2 out of our congruence to obtain:

Using the division algorithm to find an inverse we obtain:

(4)So -1 can be used as our inverse. Hence $x \equiv -20 \pmod {106}$, or rather $x \equiv 86 \pmod {106}$.

Hence, one of the solutions to our linear congruence is 86 (mod 212). To find our other solution, we will take 86 and add 106 to it. That is 86 + 106 = 192 (mod 212).

## Example 3

**Find all solutions to the linear congruence $33x \equiv 7 \pmod 143$.**

Let's first notice that $(a, m) = (33, 143) = 11$. However, $11 \nmid 7$. Hence from **4)**, this linear congruence does not have any solutions (mod 143).

## Example 4

**Find all solutions to the linear congruence $124x \equiv 132 \pmod {900}$.**

Notice that since $(124, 900) = 4$, we can simplify our congruence by dividing by 4 to obtain $31x \equiv 33 \pmod 225$. Now notice that $(a, m) = 1$, hence we can continue through in solving our congruence by finding an inverse of 31 (mod 225):

(5)Hence we can use -29 as an inverse of 31 (mod 225). We thus get that:

(6)So one of our solutions is 168 (mod 225). Our other solutions are 168 + 225 = 393, 168 + 2(225) = 618, and 168 + 3(225) = 843, all (mod 900).

## Example 5

**Find all solutions to the linear congruence $120x \equiv 52 \pmod {119}$.**

First notice that $120x \equiv 52 \pmod {119}$ is the same thing as $(30)4x \equiv (13)4 \pmod {119}$. Notice that $(4, 119) = 1$, hence it follows that we have the linear congruence $30x \equiv 13 \pmod {119}$. Now let's try to solve this by finding an inverse of 30 (mod 119).

(7)Hence we can use 4 as an inverse. We thus get that:

(8)Hence our solution is 52 (mod 119).

## Example 6

**Verify that for the linear congruence $120x \equiv 52 \pmod {119}$, all possible values of x are in the form x = 52 + 119k.**

From example 5, we know that the solution to the linear congruence $120x \equiv 52 \pmod {119}$ is 52 (mod 119). Hence, suppose x = 52 + 119k:

(9)Hence, 1 | 120 and leaves remainder 0, which is true. Hence all possible values of x are in the form x = 52 + 119k.