# 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!

• Divide both sides by $3$ and then multiply by $14$ – lab bhattacharjee Jul 22 '17 at 8:58
• @labbhattacharjee Thank you for your reply. Is there a more general definition for what you did? And what would be the solution? I know that the solution is $18$ but I don't see how you get that from what you wrote. – ViktorG Jul 22 '17 at 9:00
• See my answer here math.stackexchange.com/questions/407478/… – lab bhattacharjee Jul 22 '17 at 9:04
• Find $n$ such that $9n\equiv A \pmod {43}$ with $|A|<9.$ E.g let $9n<43<9(n+1)$ or $9(n-1)<43<9n.$ In this case take $n=5.$ Then $9x\equiv 33\iff 2x\equiv 45x\equiv (5)(33)=165 \equiv 36.$.... We could repeat this method, e.g. $2x\equiv 36 \iff x\equiv 44x\equiv (22)(2x) \equiv (22)(36),$ but the "common -divisor" short cut can be used when available : Since $\gcd(2,43)=1$ we have $2x\equiv 36 \iff (2)(x)\equiv (2)(18) \iff x\equiv 18.$..... Or we can use the "short-cut" at the start: $9x\equiv 33 \iff 3x\equiv 11 \iff -x\equiv 42x =(14)(3x)\equiv (14)(11)=154\equiv -18.$ – DanielWainfleet Jul 22 '17 at 19:51

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

• Thank you very much! We just realized our mistake :D Have a great day ! – ViktorG Jul 22 '17 at 9:12
• @ViktorG What was your mistake? – Bill Dubuque Jul 22 '17 at 18:00
• @BillDubuque we already calculated the multiplicative inverse of 9 and didn't think about multiplying both sides with it to make it simpler – ViktorG Jul 22 '17 at 23:20

There no "best" way in general. The extended Euclidean algorithm is an efficient algorithmic way to compute modular inverses & fractions, but often there are quicker ways for small or special numbers.

We show $$5$$ 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 division 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, and 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\qquad$$

\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

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

• See also this answer for a handful of methods applied to a similar problem. – Bill Dubuque Dec 1 '19 at 17:02