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

Guest May 21, 2019

#1**+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**

Guest May 21, 2019

#2**+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 \)

heureka May 22, 2019