Additional Examples Of Solving Linear Congruences

# Additional Examples of Solving Linear Congruences

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

Find all solutions to the linear congruence $5x \equiv 12 \pmod {23}$.

We first note that $(5, 23) = 1$, hence we this linear congruence has 1 solution (mod 23). 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 solution in least residue is 7 (mod 23).

## Example 2

Find all solutions to the linear congruence $210x \equiv 40 \pmod {212}$.

Let's first reduce this congruence. By property 2), we can see that we can take 2 out of our congruence to obtain:

(3)
\begin{align} 105x \equiv 20 \pmod 106 \end{align}

Using the division algorithm to find an inverse we obtain:

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

So -1 can be used as our inverse. Hence $x \equiv -20 \pmod {106}$, or rather $x \equiv 86 \pmod {106}$.

Hence, one of the solutions to our linear congruence is 86 (mod 212). To find our other solution, we will take 86 and add 106 to it. That is 86 + 106 = 192 (mod 212).

## Example 3

Find all solutions to the linear congruence $33x \equiv 7 \pmod 143$.

Let's first notice that $(a, m) = (33, 143) = 11$. However, $11 \nmid 7$. Hence from 4), this linear congruence does not have any solutions (mod 143).

## Example 4

Find all solutions to the linear congruence $124x \equiv 132 \pmod {900}$.

Notice that since $(124, 900) = 4$, we can simplify our congruence by dividing by 4 to obtain $31x \equiv 33 \pmod 225$. Now notice that $(a, m) = 1$, hence we can continue through in solving our congruence by finding an inverse of 31 (mod 225):

(5)
\begin{align} 225 = 31(7) + 8 \\ 31 = 8(3) + 7 \\ 8 = 7(1) + 1 \\ \\ 1 = 8 + 7(-1) \\ 1 = 8 + [31 + 8(-3)](-1) \\ 1 = 31(-1) + 8(4) \\ 1 = 31(-1) + [225 + 31(-7)](4) \\ 1 = 225(4) + 31(-29) \end{align}

Hence we can use -29 as an inverse of 31 (mod 225). We thus get that:

(6)
\begin{align} (-29)31x \equiv (-29)(33) \pmod {225} \\ x \equiv -957 \pmod {225} \\ x \equiv 168 \pmod {225} \end{align}

So one of our solutions is 168 (mod 225). Our other solutions are 168 + 225 = 393, 168 + 2(225) = 618, and 168 + 3(225) = 843, all (mod 900).

## Example 5

Find all solutions to the linear congruence $120x \equiv 52 \pmod {119}$.

First notice that $120x \equiv 52 \pmod {119}$ is the same thing as $(30)4x \equiv (13)4 \pmod {119}$. Notice that $(4, 119) = 1$, hence it follows that we have the linear congruence $30x \equiv 13 \pmod {119}$. Now let's try to solve this by finding an inverse of 30 (mod 119).

(7)
\begin{align} 119 = 30(3) + 29 \\ 30 = 29(1) + 1 \\ \\ 1 = 30 + 29(-1) \\ 1 = 30 + 29[119 + 30(-3)](-1) \\ 1 = 119(-1) + 30(4) \\ \end{align}

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

(8)
\begin{align} (4)30x \equiv (4)(13) \pmod {119} \\ x \equiv 52 \pmod {119} \end{align}

Hence our solution is 52 (mod 119).

## Example 6

Verify that for the linear congruence $120x \equiv 52 \pmod {119}$, all possible values of x are in the form x = 52 + 119k.

From example 5, we know that the solution to the linear congruence $120x \equiv 52 \pmod {119}$ is 52 (mod 119). Hence, suppose x = 52 + 119k:

(9)
\begin{align} 120(52 + 119k) \equiv 52 \pmod {119} \\ 6240 + 14280k \equiv 52 \pmod {119} \\ 14280k \equiv -6188 \pmod {119} \\ 14280k \equiv 0 \pmod {119} \\ (119)120k \equiv (119)0 \pmod {119} \\ 120k \equiv 0 \pmod 1 \end{align}

Hence, 1 | 120 and leaves remainder 0, which is true. Hence all possible values of x are in the form x = 52 + 119k.