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