3
$\begingroup$

I want to do inverse modulo to solve the equation

$$23x \equiv 1 \mod 120$$

And to do that I used the extended Euclidean Algorithm. $$120=23\times5+5$$ $$23=5 \times4+3$$ $$5=3\times1+2$$ $$3=2\times1+1$$ Which makes $1 \equiv3-2\times1=3-2$. I then substituted the other values to get the following


$$2=5-3\times1=5-3$$ $$1=3-(5-3)$$


$$3=23-5\times4$$ $$1=(23-5\times4)-(5-(23-5\times4))$$


$$5 \equiv120-23 \times5$$ $$1 \equiv (23-((120-23\times5)\times4)-(120-23\times5(23-((120-23\times5)\times4))$$


But now I'm not sure how much I need to simplify this down in order to find the answer.

$\endgroup$
  • $\begingroup$ Well, to construct an explicit inverse you need to find integers $a,b$ with $120a+23b=1$, or at least you need to find $b$. Note: you can simplify the original problem by noting that $120=2^3\times 3\times 5$ and solving for each factor separately, then using the Chinese Remainder Theorem. $\endgroup$ – lulu Mar 22 '18 at 12:36
3
$\begingroup$

We wish to solve the congruence $23x \equiv 1 \pmod{120}$.

You correctly obtained \begin{align*} 120 & = 5 \cdot 23 + 5\\ 23 & = 4 \cdot 5 + 3\\ 5 & = 1 \cdot 3 + 2\\ 3 & = 1 \cdot 2 + 1\\ 2 & = 2 \cdot 1 \end{align*} Now, if we work backwards, we can obtain $1$ as a linear combination of $23$ and $120$.
\begin{align*} 1 & = 3 - 2\\ & = 3 - (5 - 3)\\ & = 2 \cdot 3 - 5\\ & = 2(23 - 4 \cdot 5) - 5\\ & = 2 \cdot 23 - 9 \cdot 5\\ & = 2 \cdot 23 - 9 \cdot (120 - 5 \cdot 23)\\ & = 47 \cdot 23 - 9 \cdot 120 \end{align*} Thus, $$23 \cdot 47 \equiv 1 \pmod{120}$$ Hence, $x \equiv 47 \pmod{120}$, so $47$ is the multiplicative inverse of $23$ modulo $120$.

$\endgroup$
  • $\begingroup$ That’s the exact answe I was looking for! $9 \cdot 120$ is made equal to $0$ the iggy? $\endgroup$ – Ski Mask Mar 22 '18 at 14:19
  • $\begingroup$ Any integer multiple of $120$ is congruent to $0$ modulo $120$. $\endgroup$ – N. F. Taussig Mar 22 '18 at 14:23
1
$\begingroup$

Use the extended Euclidean algorithm to save you calculating backwards: $$\begin{array}{rrrl} r_i &u_i&v_i&q_i \\ \hline 120&0&1\\ 23&1&0&5\\ \hline 5&-5& 1&4 \\ 3&21&-4&1 \\ 2&-26&5&1\\ 1&\color{red}{47}& -9\\ \hline \end{array}$$ whence the Bézout's relation: $$47\cdot 23-9\cdot120=1$$ which says the inverse of $23$ mod. $120$ is $47$.

$\endgroup$

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.