Calculating Inverse modulo 101

Question

A lot of problems are calculating $n\mod m$ with $n<m$. But I have the following problem: Find the inverse of $71 \mod 101$. Now using Euclid, I get the $\gcd(71,101)=1$ and $$ 1=3-(1\cdot(8-2\cdot(11-1\cdot(30-2\cdot(71-2\cdot(101-71))))) $$ I know the solution is $37$ but I am not able to get there...

The above I get with: $$ 101=1\cdot71+30, 71=2\cdot30+11, 30=2\cdot11+8, 11=1\cdot8+3, 8=2\cdot3+2, 3=1\cdot2 +1 $$

How do I get the $37$?

Answer 1

$1=3-1\times2=3-1\times(8-2\times3)=3\times3-1\times8=3\times(11-1\times8)-1\times8$

$=3\times11-4\times8=3\times11-4\times(30-2\times11)=11\times11-4\times30$

$=11\times(71-2\times30)-4\times30=11\times71-26\times30=11\times71-26\times(101-71)$

$=\color{red}{37}\times71-26\times101$

Answer 2

The calculations you have already made will answer the question if worked backwards in an appropriate way.

It's also helpful to look out for shortcuts if possible. So, using your results, but starting from the relatively obvious $11\times 11-4\times 30=1$ we have $$11\times (71-2\times30)-4\times 30=1$$ $$11\times 71-26\times 30=1$$ $$11\times 71-26\times(101-71)=1$$ $$37\times 71-26\times 101=1$$

The inverse is $37$.