# 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)Hence we can use $-29$ as an inverse of $31$ modulo $225$. We will get:

(2)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)Hence we can use $4$ as an inverse of $30$ modulo $119$ to get:

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