Supposed we wish to compute $11^{-1}$ mod $25$. Using the extended Euclid algorithm, we find that $15 \cdot 25 – 34 \cdot 11 =1$. Reducing both sides modulo $25$, we have $-34 \cdot 11 \equiv 1$ mod $25$. So $-34 \equiv 16 $ mod $25$ is the inverse of $11$ mod $25$.
im realy confused about this problem, can someone go over this please and explain how this is done
Best Answer
Note that $25 | 15 \cdot 25$, so $15 \cdot 25 \equiv 0 \pmod{25}$. On the other hand, we see that
$$1 \equiv -15 \cdot 25 - 34 \cdot 11 \equiv 0 + (-34) \cdot 11 \pmod{25}$$
Finally,
$$-34 \equiv -34 + 50 \equiv 16 \pmod{25}$$
so we can rewrite the above as
$$1 \equiv 16 \cdot 11 \pmod{25}$$
and $16$ is the desired inverse.
Note that by direct computation,
$$16 \cdot 11 = 176 = 7 \cdot 25 + 1$$
Alternatively, we can use the Euclidean algorithm and find that
\begin{align*} 25 &= 2 \cdot 11 + 3 \\ 11 &= 3 \cdot 3 + 2 \\ 3 &= 1 \cdot 2 + 1 \end{align*}
Thus,
\begin{align*} 1 &= 3 - 1 \cdot 2 \\ &= 3 - 1 \cdot (11 - 3 \cdot 3) = 4 \cdot 3 - 1 \cdot 11 \\ &= 4 \cdot (25 - 2 \cdot 11) - 1 \cdot 11 = 4 \cdot 25 - 9 \cdot 11 \end{align*}
So $1 \equiv -9 \cdot 11 \equiv 16 \cdot 11 \pmod{25}$ as before.