# Extended Euclidean Algorithm yielding incorrect modular inverse

In order to solve an ElGamal cryptographic problem, I need to solve

8x≡1 (mod 17)


Or simply, find the inverse of 8 in the context of modular 17.

By the Extended Euclidean Algorithm, we get:

17=8(2)+1
=> 1=17-8(2)


So, simply, the inverse of 8 (mod 17) should be 2, but this is not the case, It is indeed 15. What am I missing here? My experience with number theory is touchy, and this code theory course requires it.

• The inverse of $8$ is $\color{red} -2$, by your calculation, and $-2\equiv 15\mod 17$. – Bernard Mar 24 '19 at 21:17

$$\bmod 17\!:\,\ 1 = 17-8(2)\equiv -8(2)\equiv 8(\color{#c00}{-2})\,$$ so $$\,8^{-1}\equiv \color{#c00}{-2}\equiv 15\ \$$
Remark  Generally $$\,\gcd(a,n)=1\,\Rightarrow\,\underbrace{ 1=ja+kn}_{\rm Bezout}\,\Rightarrow\,\bmod n\!:\ 1\equiv ja\,\Rightarrow\, j\equiv a^{-1}$$