4
$\begingroup$

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$
  • 1
    $\begingroup$ Divide both sides by $3$ and then multiply by $14$ $\endgroup$ – lab bhattacharjee Jul 22 '17 at 8:58
  • 1
    $\begingroup$ @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. $\endgroup$ – ViktorG Jul 22 '17 at 9:00
  • $\begingroup$ See my answer here math.stackexchange.com/questions/407478/… $\endgroup$ – lab bhattacharjee Jul 22 '17 at 9:04
  • $\begingroup$ 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.$ $\endgroup$ – DanielWainfleet Jul 22 '17 at 19:51
12
$\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$.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ See also this answer for a handful of methods applied to a similar problem. $\endgroup$ – Bill Dubuque Dec 1 '19 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.