<s>[INST] Calculating Inverse modulo 101 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$?
 [/INST] $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$
</s>