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.

$\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}$