We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
55
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+22358 
+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

17 Online Users

avatar
avatar
avatar