Solving Linear Congruence ax ≡ b (mod N)

How can we solve linear congruences? A tool that comes handy when it comes to solving congruences is a multiplicative inverse. A multiplicative inverse for $a$ in modulo $n$ exists if and only if $\gcd{(a,n)}=1$. A multiplicative inverse for $a$ is denoted as $a^{-1}$ where $$a\cdot a^{-1}\equiv 1\pmod{n}.$$

If the numbers are small enough, it will usually be easy to find the multiplicative inverse by guessing and checking. However, there is a way where you will find it for sure, but may take a bit longer. So now let's go through a problem.

Solve $5x+2\equiv 4\pmod{7}$ for $x$.

Solution: Like what we would do for linear equations with integers, subtract $2$ from each side, resulting in $5x\equiv 2\pmod{7}$. If you realize the multiplicative inverse of $5$ modulo $7$ is $3$, because $5\cdot 3\equiv 1\pmod{7}$, then we can multiply each side by $3$ resulting in $$(5\cdot 3)x\equiv 2\cdot 3\pmod{7}$$ $$\implies x\equiv 6\pmod{7}$$

However, if we didn't realize that the multiplicative inverse of $5$ is $3$, then we know that we are looking for some integers $m$ and $n$ such that $5n+7m=1$. Recall that we said that $\gcd(5,7)=1$ was a requirement for the equation to be solvable. This agrees with Bezout's Lemma, which says that this equation has an integer solution.

Now let's find that solution. By the division algorithm, we know $$\begin{align*} 7 &= 5(1) + 2 &\implies\qquad 2 &= 7(1) - 5(1)\\ 5 &= 2(2) + 1 &\implies\qquad 1 &= 5(1) - 2(2)\\ 2 &= 1(2) + 0 \end{align*}$$ Substituting the first equation into the second and expanding, we have $$1=5(1)-2(7(1)-5(1))=5(3)-7(2)$$ So, we know that $5\cdot 3\equiv 1\pmod{7}$. Then, we proceed in the same way. Note that this is just a small example, so it is easily guessible. When the numbers get larger, this will be more practical.

Most linear congruences can be solved this way, however, the congruences in the form $ax+b\equiv c\pmod{n}$ where $\gcd{(a,n)}$ is not equal to $1$ cannot be solved using multiplicative inverses, since there is no inverse when $\gcd{(a,n)}$ is not equal to $1$, as shown in the solution.