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