<s>[INST] Computing an inverse modulo $25$ 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
 [/INST] 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.
</s>