# Solving Linear Congruences 1

On the Existence of Solutions to Linear Congruences page we looked at some important results regarding solving the linear congruence $ax \equiv b \pmod m$:

- If $(a, m) \not \mid b$ then $ax \equiv b \pmod m$ has no solutions.

- If $(a, m) = 1$ then $ax \equiv b \pmod m$ has one solution.

- If $(a, m) = d$ and $d \mid b$ then $ax \equiv b \pmod m$ has $d$ solutions.

We will now look at finding all solutions to some linear congruences.

## Example 1

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

We first note that $(5, 23) = 1$, hence this linear congruence has one solution. 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 only solution is $x = 7$.

## Example 2

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

Notice that $(210, 212) = 2$, and so $210x \equiv 40 \pmod {212}$ will have two solutions.

Now this linear congruence can be reduced to $105 \equiv 20 \pmod {106}$ which has only one solution (which is also a solution to the earlier linear congruence) and if $x_0$ is this solution, then $x_0 + 106$ is the second solution to the original linear congruence. Now, using the division algorithm we have that:

(3)So we may use $-1$ as an inverse, and hence:

(4)Hence $x = 86, 192$ are the solutions to this linear congruence.

## Example 3

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

We have that $(33, 143) = 11$ but $11 \not \mid 7$, so $33x \equiv 7 \pmod {143}$ has no solutions.