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!
$\endgroup$ 44 Answers
$\begingroup$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$.
$\endgroup$ 3 $\begingroup$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$$
$$\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.
$\endgroup$ 1 $\begingroup$$43$ is prime. And even if it weren't, $\gcd(9,43)= 1$.
That means we know that $9^{-1}_{43}$ exists. That is there is a number so that $9\cdot 9^{-1}_{43} \equiv 1 \pmod {43}$. And we could calculate (or guess) that $9^{-1}_{43}\equiv 24$ (because $9\cdot 24\equiv 1 \pmod {43}$) and we can solve $9x \equiv 33\pmod {43} \implies 24\cdot 9 x\equiv x \equiv 24\cdot 33\pmod {43}$.
But we don't have to. If $\gcd(9,43) =1$ and if $9^{-1}$ exists, then in this case we are allows to know that division is acceptable, and we are, in this case, allowed to divide both sides by $3$.
$9x \equiv 33 \pmod {43}$
$3x\equiv 11 \pmod {43}$ (we wouldn't be allowed to do this if $\gcd(3,43)\ne 1$)
Now $3$ is such a small number that we know that one these: $11, 11 + 43, 11+2*43$ is divisible by $3$.
As it turns out $3x \equiv 11 \equiv 11 + 43 \equiv 54\pmod {43}$.
And we can divide both sides by $3$ to get
$x \equiv 18\pmod {43}$.[1]
..........
Alternatively we can do baby steps.
$9x \equiv 33 \pmod {43} \implies$ there is a $k$ so that
$9x = 33 + 43k$. Divide by $3$ and we get
$3x = 11 + 43\frac k3$. That will be an integer so long as we choose a $k$ that is divisible by $3$. Relable $m= \frac k3$
$3x = 11 + 43m$
$3x =11 + 43 + 43(m-1)$
$3x = 54 +43(m-1)$
$x = 18 + 43\frac {m-1}3$ which is an integer so long as we select $m-1$ so that $m-1$ is divisible by $3$. (For example the easiest example is $m-1=0$, $m=1$, $k = 3$ an $9*18 = 33 + 3\cdot 43$. But we don't need to find the actually $k$)
......
[1] Notice our earlier answer $24\cdot 33\equiv 24\cdot 32 + 24\equiv 48\cdot 16 + 24 \equiv 5\cdot 16 + 24\equiv 80 + 24 \equiv 86 + 18 \equiv 18\pmod {43}$. So our answers are consistent.
$\endgroup$ $\begingroup$$\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{9}{x}\equiv\mathrm{33}\left({mod}\mathrm{43}\right)\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \\ $$\mathrm{3}{x}\equiv\mathrm{11}\left({mod}\mathrm{43}\right)\equiv\mathrm{54}\left({mod}\mathrm{43}\right) \\ $$\:\:\:\:\:\:\:\:\:\:\:\:\:{x}\equiv\mathrm{18}\left({mod}\mathrm{43}\right)\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \\ $
$\endgroup$ 1
