2
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Perfect! I should have been thinking of it as 17+(8*-2), thank you (will accept when the timer allows)! $\endgroup$ Mar 24, 2019 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .