Thread: Inverse of a modulo

1. Inverse of a modulo

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

2. Originally Posted by knguyen2005
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 ?
This means $\displaystyle 43(32) \equiv 1 (\bmod 125)$ therefore $\displaystyle 32$ is inverse of $\displaystyle 43$.

After this, how can I solve the equation 43x = 3 mod 125?
Multiply both sides by $\displaystyle 32$ and this gives $\displaystyle 32(43x) \equiv 32(3) (\bmod 125) \implies x \equiv 96 (\bmod 125)$.