Find the inverse of $2$ modulo $17$ using the Euclidean algorithm
The question states "find the inverse of a modulo m for each of these pairs of relatively prime integers"
ATTEMPT AT SOLUTION\begin{align*} 17 & = 2 \cdot 8 + 1\\ 2 & = 1 \cdot 2 \end{align*}
Thus, $\gcd(2, 17) = 1$ and it does have an inverse
Reversing the Euclidean expansion, I get $$1 = 17 \cdot 1 - 2 \cdot 8$$
and thus the Bézout coefficients of $2$ and $17$ are $1$ and $-8$, and the inverse of $2$ modulo $17$ is $8$.
However, when I check my answer, the inverse of $2$ modulo $7$ is $9$! Please tell me what I am doing wrong here!
$\endgroup$ 21 Answer
$\begingroup$Observe that you actually got
$$1=17\cdot1+2\cdot(-8)\implies -8=2^{-1}\pmod{17}$$
but of course $\;-8=9\pmod{17}\;$ , so you only had a tiny sign mistake.
$\endgroup$
