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)

\begin{align} 23 &= 5(4) + 3 \\ 5 &= 3(1) + 2 \\ 3 &= 2(1) + 1 \\ \\ 1 &= 3 + 2(-1) \\ 1 &= 3 + [5 + 3(-1)](-1) \\ 1 &= 5(-1) + 3(2) \\ 1 &= 5(-1) + [23 + 5(-4)](2) \\ 1 &= 23(2) + 5(-9) \end{align}

Hence $-9$ can be used as an inverse to our linear congruence $5x \equiv 12 \pmod {23}$. Thus:

(2)

\begin{align} (-9)5x \equiv (-9)12 \pmod {23} \\ x \equiv -108 \pmod {23} \\ x \equiv 7 \pmod {23} \end{align}

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)

\begin{align} \quad 106 &= (105)(1) + 1 \\ \quad 105(-1) + 106(1) &= 1 \end{align}

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

(4)

\begin{align} \quad (-1)105x & \equiv (-1)20 \pmod {106} \\ \quad x & \equiv -20 \pmod {106} \\ \quad x & \equiv 86 \pmod {106} \end{align}

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.