+0  
 
0
109
5
avatar+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
avatar
0

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"

 Jul 10, 2020
 #2
avatar+110689 
+2

Please show your logic.

Melody  Jul 10, 2020
 #3
avatar
-1

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

Guest Jul 10, 2020
 #4
avatar+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
avatar+110689 
0

Thank Max, another one for me to ponder :)

Melody  Jul 11, 2020

21 Online Users

avatar
avatar