1

I can't seem to understand why the inverse of $2 \mod 127=64$

I used the Euclidean algorithm:

$2x=1 \mod127$

$127=63\cdot 2+1$

$1=127-63\cdot 2 \mod127$

$x=63$?

I'm pretty sure it's a really stupid error....please help!

Iulia
  • 1,306
Probably Lost
  • 97
  • 2
    You forgot the minus. – quid Feb 13 '15 at 19:44
  • 1
    As quid indicated, one solution is $-63$. If you add $127$ to $-63$, you will obtain the residue $64$. $2^{-1} \equiv 64 \pmod{127}$ since $2 \cdot 64 \equiv 128 \equiv 1 \pmod{127}$. The set of all inverses is $64 + 127n, n \in \mathbb{Z}$. The solution you found corresponds to the choice $n = -1$. – N. F. Taussig Feb 13 '15 at 20:28

2 Answers2

1

$2\times 64=128\equiv 1\mod (127)$

Samrat Mukhopadhyay
  • 16,277
0

More simply: $\ {\rm mod}\ m = 2n\!-\!1\!:\,\ 2n\equiv 1\,\Rightarrow\, 2^{-1}\equiv n\equiv (m\!+\!1)/2\,\ $ [$\equiv (127\!+\!1)/2\equiv 64$ ]

Remark $\ $ The same idea works to compute $\, a^{-1}\!\pmod{an\pm1},\,$ i.e. when $\,m \equiv \pm1\pmod{a}$. This will often be simpler than using the Extended Euclidean algorithm, so may help to avoid errors, such as your omitting the sign on $\,63.$

Community
  • 1
Bill Dubuque
  • 272,048