Find a solution for 23x=5 (mod 60)

Question

The topic is euclidean algorithm and GCD. This is a simple question, but I'm just stuck finding an inverse for 23 in $Z_{60}$.

I performed the algorithm and proved that 23 and 60 are coprime, so there is a single inverse.

Answer 1

We perform the Extended Euclidean Algorithm:

\begin{align} 60 &= 2 \cdot 23 + 14 \\ 23 &= 1 \cdot 14 + 9 \\ 14 &= 1 \cdot 9 + 5 \\ 9 &= 1 \cdot 5 + 4 \\ 5 &= 1 \cdot 4 + 1 \end{align}

Working backwards, we can write \begin{align} 1 &= 5 - 1 \cdot 4 \\ &= 5 - (9 - 1 \cdot 5) \\ &= 2 \cdot 5 - 1 \cdot 9 \\ &= 2 \cdot (14-1 \cdot 9) - 1 \cdot 9 \\ &= 2 \cdot 14 - 3 \cdot 9\\ &= 2 \cdot 14 - 3 \cdot (23 - 1 \cdot 14) \\ &= 5 \cdot 14 - 3 \cdot 23 \\ &= 5 \cdot (60 - 2 \cdot 23) - 3 \cdot 23 \\ &= 5 \cdot 60 - 13 \cdot 23. \end{align}

Looking at $1 = 5 \cdot 60 - 13 \cdot 23$ we find \begin{align} -13 \cdot 23 \equiv 47 \cdot 23 \equiv 1 \mod 60. \end{align}

Multiplying with $5$: \begin{align} 23 \cdot 47 \cdot 5 \equiv 5 \mod 60 \end{align}

So the solution $\overline{x}$ in $\mathbb{Z}_{60}$ is given by

\begin{align} \overline{x} = \overline{47 \cdot 5} = \overline{55}. \end{align}