What is the multiplicative inverse of $9\pmod{37}$?
I've done the Euclidean algorithm and found the gcd is $1$. I'm stuck on using the extended Euclidean algorithm. I'm confused because I'm left with $$37=(9\times 4)+1$$ and can't substitute it anywhere.
[Math] Multiplicative Inverse Question
modular arithmeticnumber theory
Best Answer
$37=9\cdot 4 + 1$ therefore $9\cdot 4 + 1\equiv 0\pmod{37}$
$9\cdot 4 \equiv -1\pmod{37}$
$9\cdot (-4)\equiv 1\pmod{37}$
$9\cdot (37-4)\equiv 1\pmod{37}$