Solve $23x \equiv 1 \mod 120$ using Euclidean Algorithm 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. 
 A: 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$.
A: 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$.
