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.
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}$
No comments:
Post a Comment