elementary number theory - What is the best way to solve modular arithmetic equations such as $9x equiv 33 pmod{43}$?

What is the best way to solve equations like the following:

$9x \equiv 33 \pmod{43}$

The only way I know would be to try all multiples of $43$ and $9$ and compare until I get $33$ for the remainder.

Is there a more efficient way ?

Help would be greatly appreciated!

Answer

How would we solve it in $\mathbb{R}$? Divide both sides by $9$ of course—or, in other words, multiply both sides by the multiplicative inverse of $9$. This setting is no different.

The challenge is knowing the multiplicative inverse of $9$ in $\mathbb{Z}_{43}$. What is key$^\dagger$ is that $\gcd(9,43)=1$, which guarantees integers $n$ and $m$ such that $9n + 43m = 1$. Modding out by $43$, we see that $9n \equiv 1 \pmod{43}$. Thus, multiplying both sides of $9x \equiv 33 \pmod{43}$ by $n$ gives us $x$.

The integers $n$ and $m$ can be found by using the extended Euclidean algorithm.

---

$^\dagger$ This coprimality condition is if-and-only-if. An integer $x$ will not have a multiplicative inverse $(\text{mod} \ n)$ if $\gcd(x,n) \neq 1$.