what is the modular inverse of 11 , modulo 1000?
Express your answer as an integer from 0 to 999 , inclusive.
what is the modular inverse of 11 , modulo 1000?
The answer =91, because:
[91 x 11] mod 1000 = 1, which is the definition of "modular multiplicative inverse"
Let x≡11−1(mod1000)
Now, because 11φ(1000)≡1(mod1000), where φ(x) is the Euler totient function,
x≡11φ(1000)−1(mod1000)
We proceed to find the value of φ(1000).
φ(1000)=1000(1−12)(1−15)=400
Therefore
x≡11399(mod1000)
x≡1331133(mod1000)x≡331133(mod1000)
Now,
331133≡3(mod8)
331133≡8133≡332=76⋅9≡9216≡91(mod125)
By CRT, x≡331133≡91(mod1000)
This means 11−1≡91(mod1000).