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.
Best Answer
$\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}$