Additional Examples Of Solving Linear Congruences 2

# 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)
\begin{align} 145 = 81(1) + 64 \\ 81 = 64(1) + 17 \\ 64 = 17(3) + 13 \\ 17 = 13(1) + 4 \\ 13 = 4(3) + 1 \\ 1 = 13 + 4(-3) \\ 1 = 13 + [17 + 13(-1)](-3) \\ 1 = 17(-3) + 13(4) \\ 1 = 17(-3) + [64 + 17(-3)](4) \\ 1 = 64(4) + 17(-15) \\ 1 = 64(4) + [81 + 64(-1)](-15) \\ 1 = 81(-15) + 64(19) \\ 1 = 81(-15) + [145 + 81(-1)](19) \\ 1 = 145(19) + 81(-34) \end{align}

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

(2)
\begin{align} (-34)84x \equiv (-34)33 \pmod {145} \\ x \equiv -1122 \pmod {145} \\ x \equiv 38 \pmod {145} \end{align}

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)
\begin{align} 61 = 32(1) + 29 \\ 32 = 29(1) + 3 \\ 29 = 3(9) + 2 \\ 3 = 2(1) + 1 \\ 1 = 3 + 2(-1) \\ 1 = 3 + [29 + 3(-9)](-1) \\ 1 = 29(-1) + 3(10) \\ 1 = 29(-1) + [32 + 29(-1)](10) \\ 1 = 32(10) + 29(-11) \\ 1 = 32(10) + [61 + 32(-1)](-11) \\ 1 = 61(-11) + 32(21) \end{align}

Hence 21 can be used as our inverse and thus:

(4)
\begin{align} (21) 32x \equiv (21) 14 \pmod {61} \\ x \equiv 294 \pmod {61} \\ x \equiv 50 \pmod {61} \end{align}

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)
\begin{equation} 31 = 5(6) + 1 1 = 31(1) + 5(-6) \end{equation}

Hence we can use -6 as an inverse. We thus get that:

(6)
\begin{align} (-6)5x \equiv (-6)9 \pmod {31} \\ x \equiv -54 \pmod {31} \\ x \equiv 8 \pmod {31} \end{align}

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)
\begin{align} 666 = 205(3) + 51 \\ 205 = 51(4) + 1 \\ 1 = 205 + 51(-4) \\ 1 = 205 + [666 + 205(-3)](-4) \\ 1 = 666(-4) + 205(13) \end{align}

Hence 13 can be used as an inverse. We thus get that:

(8)
\begin{align} (13)205x \equiv (13)116 \pmod {666} \\ x \equiv 1508 \pmod {666} \\ x \equiv 176 \pmod {666} \end{align}

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.