+0

# I don't understand this

0
109
5
+172

what is the modular inverse of 11 , modulo 1000?

Express your answer as an integer from 0 to 999 , inclusive.

Jul 10, 2020

#1
0

what is the modular inverse of 11 , modulo 1000?

[91 x 11] mod 1000 = 1, which is the definition of "modular multiplicative inverse"

Jul 10, 2020
#2
+110689
+2

Melody  Jul 10, 2020
#3
-1

int[1000 / 11] = 91. Hence, [11 x 91] mod 1000 = 1

Guest Jul 10, 2020
#4
+8340
+1

Let $$x \equiv 11^{-1}\pmod{1000}$$

Now, because $$11^{\varphi(1000)} \equiv 1 \pmod{1000}$$, where $$\varphi(x)$$ is the Euler totient function,

$$x\equiv 11^{\varphi(1000) - 1} \pmod{1000}$$

We proceed to find the value of $$\varphi(1000)$$.

$$\varphi(1000) = 1000\left(1 - \dfrac12\right)\left(1 - \dfrac15\right) = 400$$

Therefore

$$x\equiv 11^{399} \pmod{1000}$$

$$x\equiv 1331^{133} \pmod{1000}\\ x\equiv 331^{133}\pmod{1000}$$

Now,

$$331^{133}\equiv 3 \pmod 8$$

$$331^{133}\equiv 81^{33}\equiv3^{32} = 7^6 \cdot 9 \equiv 9216 \equiv 91\pmod{125}$$

By CRT, $$x \equiv 331^{133}\equiv 91 \pmod{1000}$$

This means $$11^{-1} \equiv 91 \pmod{1000}$$.

Jul 11, 2020
#5
+110689
0

Thank Max, another one for me to ponder :)

Melody  Jul 11, 2020