+0  
 
0
199
2
avatar

Find $2^{-1} \pmod{185}$, as a residue modulo 185. (Give an answer between 0 and 184, inclusive.)

 May 21, 2019
 #1
avatar
+1

%%time a = 2 m =185 def modInverse(a, m) : a = a % m for x in range(1, m) : if ((a * x) % m == 1) : return x print("The MMI = ", modInverse(a, m)) 

The MMI = 93 - Modular Multiplicative Inverse

 May 21, 2019
 #2
avatar+23910 
+2

Find \(2^{-1} \pmod{185}\), as a residue modulo 185. (Give an answer between 0 and 184, inclusive.)

 

According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
  \( {\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}\)
where   \({\displaystyle \phi } \) is Euler's totient function.  
A modular multiplicative inverse can be found directly:
   \({\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}\)

 

2 must be coprime to 185 or \(gcd(2, 185) = 1~ \checkmark\)

 

\(\begin{array}{|rcll|} \hline && 2^{-1}{\pmod {185}} \quad & | \quad 185 = 5\cdot 37 \\ &\equiv& 2^{\phi (185)-1}{\pmod {185}} \quad &| \quad \phi (185) = 185\left(1-\dfrac{1}{5} \right)\left(1-\dfrac{1}{37} \right)= 144 \\ &\equiv& 2^{144-1}{\pmod {185}} \\ &\equiv& 2^{143}{\pmod {185}} \quad & | \quad 2^{11} = \mathbf{13} \pmod{185} \\ &\equiv& 2^{11*13}{\pmod {185}} \\ &\equiv& \left(2^{11} \right)^{13} {\pmod {185}} \\ &\equiv& \mathbf{13}^{13} {\pmod {185}} \quad & | \quad 13^{5} = \mathbf{-2} \pmod{185} \\ &\equiv& 13^{5*2+3}{\pmod {185}} \\ &\equiv& \left(13^{5} \right)^{2}*13^3 {\pmod {185}} \\ &\equiv& \left(\mathbf{-2}\right)^{2}*13^3 {\pmod {185}} \\ &\equiv& 4*13^3 {\pmod {185}} \\ &\equiv& 8788 {\pmod {185}} \\ &\equiv& \mathbf{93} {\pmod {185}} \\ \hline \end{array}\)

 

The modular multiplicative inverse of 2 is 93

 

\(Proof: 2 * 93 = 186 \equiv 1 \pmod{185} ~ \checkmark \)

 

laugh

 May 22, 2019

32 Online Users

avatar