Solve $23x \equiv 1 \mod 120$ using Euclidean Algorithm

Question

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.

Answer 1

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

Answer 2

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