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)

\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$ modulo $145$. We get:

(2)

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

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)

\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$.

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)

\begin{align} 31 & = 5(6) + 1 \\ 1 & = 31(1) + 5(-6) \end{align}

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 = 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)

\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 = 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.