# Additional Examples of Solving Linear Congruences 2

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

**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 a modular inverse of 81 (mod 145) by the division algorithm:

(1)Hence -34 can be used as an inverse of 81 (mod 145). We thus get that:

(2)Hence our 1 solution is 38 (mod 148).

## Example 2

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

We note that $(64, 122) = 2$, and that 2 | 28. Hence we will have precisely 2 solutions (mod 122). First, let's reduce this congruence down using property 2 to get that $32x \equiv 14 \pmod {61}$. Now let's solve this congruence by finding an inverse of 32 (mod 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. Hence our only two solutions are 50 and 111.

## Example 3

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

We first note that $(20, 124) = 4$, and 4 | 36, hence there are precisely 4 solutions to this congruence. We will first simplify this congruence down by reducing the congruence by 4: $5x \equiv 9 \pmod {31}$. Now we will find a modular inverse of 5 (mod 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, 8 + 31(2), and 8 + 31(3) are solutions to our original congruence. More precisely, our solutions are 8, 39, 70, 101.

## Example 4

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

We note that $(410, 1332) = 2$, and that 2 | 232, hence our linear congruence has precisely 2 solutions. Dividing our congruence by 2, we obtain that $205x \equiv 116 \pmod {666}$. Now we'll apply the division algorithm to find an inverse of 205 (mod 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, or more precisely 842.

## Example 5

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

We note that $(1232, 1442) = 14$. However, 14 does not divide 339, hence there are no solutions to this linear congruence.