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$.
No comments:
Post a Comment