Solving Linear Congruences 2

# Solving Linear Congruences 2

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

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$. Using the division algorithm and we have that:

(1)
\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$ modulo $225$. We will get:

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

So our solutions are $x = 168, 393, 618, 843$.

## Example 2

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 $30x \equiv 13 \pmod {119}$. Now, using the division algorithm and we get:

(3)
\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 of $30$ modulo $119$ to get:

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

Hence our solution is $x = 52$.

## Example 3

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

From example 5, we know that the solution to the linear congruence $120x \equiv 52 \pmod {119}$ is $x = 52$ (mod 119). Suppose that $x = 52 + 119k$ for any $k \in \mathbb{Z}$. Then:

(5)
\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 all possible values of $x$ are in the form $x = 52 + 119k$.