# Extended Euclidean Algorithm (the going backwards step) and modular inverses

I have two questions.

1. When computing the modular inverse of a number (computing $x^{-1} \bmod m$), in practice do people actually do "Mentally, what multiple of $x$, taken mod $m$, has a remainder of $1$?"

2. I don't understand the Extended Euclidean Algorithm. I know how to get $\gcd(a,b)$ using the normal Euclidean Algorithm and how to write the modular equations out in the form $a = qp + r$. For example $\gcd(\color{blue}{22},\color{red}{6})$ implies an equation $\color{blue}{22} = (3)(\color{red}{6}) + \color{green}{4}$ which leads to $\gcd(\color{red}{6},\color{green}{4})$. But I don't understand how you "back up" from the final step (when you compute the final gcd once $b=0$) to get the original terms $x,y$ in the first modular equation.

I hope this makes sense. Thanks.

• For the first question, remove the word "multiple of "x" and substitute with "y mod m". – Paolo Leonetti Jan 11 '16 at 15:04
• @jordan I'm not sure what you mean exactly. What I mean is "What is $11^{-1} \bmod 7$? The multiples of $11$ are $11, 22, 33, 44, 55, 66, 77, 88, 99, ...$ and their results mod $7$ are $4, 1, ...$ and at this point I stop and see that the correct multiplier is $2$, so the inverse of $11$ mod $7$ is $2$. I could probably reduce that problem mod $7$ to begin with and compute $4^{-1} \bmod 7$. – AJJ Jan 11 '16 at 15:15
• The trial method is OK for small $m$, on the average you have to test order $m/2$ products. With the Extended Euclidean Algorithm the number of steps grows like $\log(m)$ not like $m$. And normally you do no backward steps but keep two additional sequences (or one if you want to compute modular inverses), see en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Description. – gammatester Jan 11 '16 at 15:35
• I have seen the wiki but I don't understand any of it, which is why I made this question – AJJ Jan 11 '16 at 15:49