<s>[INST] Find a number $b$ such that $a\cdot b\equiv 1\mod m$ Given two integers $a$ and $m$, such that $a\mathop\bot m,$ how can I find an integer $b$ such that $a\cdot b\equiv 1\mod m?$
 [/INST] I will show by example, $a = 7$ and $m = 17$.
I want to solve $7b + 17y = 1$ because reducing that equation mod $m$ gives $7 \cdot b \equiv 1 \pmod {17}$.
To solve $7b + 17y = 1$ I will reduce it to an easier equation $7b + (7 + 10)y = 7(b+y) + 10y = 7(b+2y) + 3y = 1$, so now we are in a similar situation.
We want to solve $7x + 3y = 1$ and we can do the same kind of reduction, $7x+3y=4x+3(x+y)=x+3(2x+y)=1$ so again we are in the same situation.
Now we want to solve $x + 3z = 1$, that is easy, set $x = 4$ and $z = -1$.. but now we have to go backwards through this to get $b$. $-1 = z = 2x+y$ and $x=4$ so $y = -9$, further $4 = x = b+2y = b-18$ so $b = 22$.
Since this is a very long calculation is it useful to check that this is the right answer: $7 \cdot 22 \equiv 7 \cdot 9 \equiv 1 \pmod {17}$.

Once this idea is very clear it is possible to optimize it so that both forward and backward stages are done simultaneously.
</s>