Having some trouble working my way back up the Extended Euclidean Algorithm. I'm trying to find the multiplicative inverse of $497^{-1} (mod 899)$. So I started working my way down first finding the gcd:

\begin{align} 899&=497\cdot1 + 402\\ 497&=402\cdot1 + 95\\ 402&=95\cdot4 + 22\\ 95&=22\cdot4 + 7\\ 22&=7\cdot3 + 1 \end{align} Now I work my way back up using the extended algorithm and substituting: \begin{align} 1&=22-(7\cdot3)\\ 1&=22-(95-(22\cdot4))\cdot3\\ 1&=22-(95-(402-(95\cdot4)\cdot4))\cdot3\\ 1&=22-(95-(402-((497-402)\cdot4)\cdot4))\cdot3\\ 1&=22-(95-(402-((497-(899-497))\cdot4)\cdot4))\cdot3\\ \end{align}

Am I going about this right? Do I just keep substituting up the chain? It gets difficult to follow for me. And Here's what the terms equal going up:

\begin{align} 7&=95-(22\cdot4)\\ 22&=402- ( 95\cdot4)\\ 95&=497- 402\\ 402&=899- 497\\ \end{align}

  • 1
    $\begingroup$ should be $1=13 \cdot 22-3 \cdot 95$ $\endgroup$ – randomgirl Oct 31 '15 at 4:49
  • $\begingroup$ Okay I think I get it. Going to go down them all and edit my post when finished. Thanks for the help so far. $\endgroup$ – pfinferno Oct 31 '15 at 4:51
  • $\begingroup$ Awesome! Makes sense now. It wasn't clicking how everything was grouping together as I went up, but it's easy now that I see it. Thank you! $\endgroup$ – pfinferno Oct 31 '15 at 5:14

For an (iterative) implementation it is easier to compute the inverse resp. the Bezout coefficients while going down.

You start with $0·497 \equiv r_0=899\mod899$ and $1·497 \equiv r_1=497\mod899$ and apply the same sequence of computations as to the remainder to the quotient sequence starting with $u_0=0, u_1=1$. \begin{align} r_2&=r_0-1·r_1&\implies u_2&=u_0-1·u_1=-1 &:&&-1·497 &\equiv r_2=402\mod899 \\ r_3&=r_1-1·r_2&\implies u_3&=u_1-1·u_2=2 &:&&2·497 &\equiv r_3=95\mod899 \\ r_4&=r_2-4·r_3&\implies u_4&=u_2-4·u_3=-9 &:&&-9·497 &\equiv r_4=22\mod899 \\ r_5&=r_3-4·r_4&\implies u_5&=u_3-4·u_4=38 &:&&38·497 &\equiv r_5=7\mod899 \\ r_6&=r_4-4·r_5&\implies u_6&=u_4-3·u_5=-123 &:&&-123·497 &\equiv r_6=1\mod899 \end{align} Thus the inverse is $-123$ or in the same equivalence class $899-123=776$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.