Find the inverse of modulo 125. Hence solve 43x = 3 mod 125?
where " = " indicates equivalent to
Firstly, I find gcd (125,43) = 1
By Euclid's algorithm, we have
125 = 43(2) + 39
43 = 39(1) + 4
39 = 4(9) + 3
4 = 3(1) +1
so, working backwards we get:
1 = 4 - 3(1)
= 4 -[39 - 4(9)](1)
= 4(10) - 39(1)
= [43 - 39(1)](10) - 39(1)
= 43(10) - 39(11)
= 43(10) - [125 - 43(2)](11)
= 43(32) - 125(11)
This means 32 is the inverse of 43 and -11 is the inverse of 125. Are these the correct results ?
After this, how can I solve the equation 43x = 3 mod 125?
Is there a quick way to find the inverse of a modulo m , apart from Euclid's algorithm