Loading [MathJax]/jax/output/SVG/fonts/TeX/fontdata.js
 
+0  
 
0
985
5
avatar+174 

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+118703 
+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+9675 
+2

Let x111(mod1000)

 

Now, because 11φ(1000)1(mod1000), where φ(x) is the Euler totient function,

x11φ(1000)1(mod1000)

 

We proceed to find the value of φ(1000).

φ(1000)=1000(112)(115)=400

 

Therefore

x11399(mod1000)

x1331133(mod1000)x331133(mod1000)

 

Now, 

3311333(mod8)

3311338133332=769921691(mod125)

 

By CRT, x33113391(mod1000)

 

This means 11191(mod1000).

 Jul 11, 2020
 #5
avatar+118703 
0

Thank Max, another one for me to ponder :)

Melody  Jul 11, 2020

0 Online Users