# Solving Linear Congruences 3

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 some more examples of finding all solutions linear congruences.

## Example 1

**Solve the linear congruence $81x \equiv 33 \pmod {145}$.**

We first note that $(81, 145) = 1$, hence there is $1$ solution to this congruence. We can find this solution by "isolating x", that is finding the inverse of $81$ modulo $145$ by the division algorithm:

(1)Hence $-34$ can be used as an inverse of $81$ modulo $145$. We get:

(2)Hence our solution is $38$.

## Example 2

**Solve the linear congruence $64x \equiv 28 \pmod {122}$.**

We note that $(64, 122) = 2$, and that $2 \mid 28$. Hence we will have precisely $2$ solutions modulo $122$. First, let's reduce this congruence to get that $32x \equiv 14 \pmod {61}$. Now let's solve this congruence by finding an inverse of $32$ modulo $61$ with the division algorithm:

(3)Hence $21$ can be used as our inverse and thus:

(4)Hence one of our solutions is $50$. Our second solution is $50 + 61 = 111$.

## Example 3

**Solve the linear congruence $20x \equiv 36 \pmod {124}$.**

We first note that $(20, 124) = 4$, and $4 \mid 36$. Hence, there are precisely $4$ solutions to this congruence. We will first simplify this congruence down by reducing the congruence to $5x \equiv 9 \pmod {31}$. Now we will find the inverse of $5$ modulo $31$ with the division algorithm:

(5)Hence we can use $-6$ as an inverse. We thus get that:

(6)Hence $x = 8$ is one of our solutions. Additionally, $8 + 31 = 39$, $8 + 31(2) = 70$, and $8 + 31(3) = 101$ are solutions to our original linear congruence.

## Example 4

**Solve the linear congruence $410x \equiv 232 \pmod {1332}$.**

We note that $(410, 1332) = 2$, and that $2 \mid 232$. Hence our linear congruence has precisely $2$ solutions. Dividing our congruence by $2$ and we obtain $205x \equiv 116 \pmod {666}$. Now we'll apply the division algorithm to find an inverse of $205$ modulo $666$:

(7)Hence $13$ can be used as an inverse. We thus get that:

(8)Hence $176$ is one of our solutions, and our other solution is $176 +666 = 842$.

## Example 5

**Solve the linear congruence $1232x \equiv 339 \pmod {1442}$.**

We note that $(1232, 1442) = 14$. However, $14 \not \mid 339$ and so there are no solutions to this linear congruence.