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!

Solution 1:

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

Solution 2:

Generally the extended Euclidean algorithm is an efficient algorithmic way to compute modular inverses & fractions, but often there are simpler ways for small or special numbers, e.g. below we give six ways to compute $\ x\equiv 33(9^{-1})=: \dfrac{33^{\phantom{|}}\!}9\equiv\dfrac{-10}9\pmod{\!43} =$ unique root of $\, 9x\equiv 33$

Cancel invertible factor $3$ then $\rm\color{#c00}{twiddle}\,$(add $\,\pm 43j\,$ to make quotient exact, cf. inverse reciprocity)

$$\dfrac{33}9\equiv \dfrac{\color{#c00}{11}}3 \equiv \dfrac{\color{#c00}{54}}3\equiv 18$$

Factor the fraction then $\rm\color{#c00}{twiddle}$ the top

$$\dfrac{-10}9\equiv \dfrac{\color{#c00}{-2}}9\ \dfrac{5}1\equiv\dfrac{\color{#c00}{-45}}9\ \dfrac{5}1\equiv -5\cdot 5\equiv 18$$

Gauss's algorithm

$$\dfrac{-10}9\equiv \dfrac{-50}{45}\equiv\dfrac{-50}2\equiv -25\equiv 18$$

Extended Euclidean algorithm in forward equational form, then its associated fractional form

$$ \begin{array}{rr} \bmod 43\!:\ \ \ \ \ \ \ \ [\![1]\!] &43\, x\,\equiv\ \ 0\ \\ [\![2]\!] &\ \color{#c00}{9\,x\, \equiv -10}\!\!\!\\ [\![1]\!]-5\,[\![2]\!] \rightarrow [\![3]\!] & \color{#0a0}{-2\,x\, \equiv\ \ 7}\ \\ [\![2]\!]+\color{orange}4\,[\![3]\!] \rightarrow [\![4]\!] & \color{#90f}{1\,x\, \equiv 18}\ \end{array}\qquad\qquad\ $$

$$x\,\equiv\, \dfrac{0}{43}\ \overset{\large\frown}\equiv \underbrace{\color{#c00}{\dfrac{-10}{9}}\ \overset{\large\frown}\equiv \ \color{#0a0}{\dfrac{7}{-2}}\ \overset{\large\frown}\equiv\ \color{#90f}{\dfrac{18}{1}}} _{\!\!\!\Large \begin{align}\color{#c00}{-10}\ \ + \ \ &\!\color{orange}4\,(\color{#0a0}{\ \, 7\ \, }) \ \ \equiv \ \ \color{#90f}{18}\\ \color{#c00}{9}\ \ +\ \ &\!\color{orange}4\,(\color{#0a0}{-2} ) \ \ \equiv\ \ \ \color{#90f}{1}\end{align}}\quad $$

Fractional extension of the binary extended Euclidean algorithm, which uses only cancellation of $2$ and mediant subtraction $\ \frac{a}b\ominus \frac{c}d := \frac{a-c}{b-d}\pmod{\!43}$

$$\begin{align} &\dfrac{43}{43}\bmod \dfrac{33}9 \equiv \dfrac{15}8\ \left[\:\! {\rm by}\,\ \dfrac{43}{43}\ominus\dfrac{33}9 \equiv \dfrac{10}{34}\equiv \dfrac{5}{17};\ \ \dfrac{5}{17}\ominus \dfrac{33}9 \equiv\dfrac{15}8\right]\\[.6em] &\dfrac{33}9 \bmod \dfrac{15}8 \equiv\color{#90f}{\dfrac{18}1}\ \left[\:\! {\rm by}\,\ \dfrac{33}9\ominus \dfrac{15}8\equiv \dfrac{18}1\right] \end{align}$$

There is an analogous fractional "reverse" Euclidean algorithm for computing modular inverses and fractions for polynomials $\,f(x)\,$ over a field, using only cancellation of $x$ and (scaled) mediant addition / subtraction $\,\frac{f}g\:\!\oplus\:\! c\!\cdot \!\frac{f'}{g'} := \frac{f+cf'}{g+c\:\!g'},\,$ e.g. see Joe Silverman's note and this question on such, where the modulus is $\,x^n-1\,$ so cancellation of $x = $ multiplication by $x^{-1}\equiv x^{n-1}\,$ is a trivial cyclic shift (analogous to the fact here that cancelling $2$ is trivial: if the numerator is odd then add or subtract the odd modulus to to get an even rep, then cancel $2$ from the even numerator and denominator, as explained here). Note: JS's presentation does not use the above fractional or reverse / localized Euclidean viewpoint but instead uses essentially elementary row operations as in standard algorithms for computing Hermite / Smith normal forms.

We can also use Newton's method (Hensel lifting) to lift inverses to higher powers, e.g. see here.

See here for general theory and algorithms to solve a linear congruence $\,ax\equiv b\pmod{\! n}$

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.