+0

0
101
2

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

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

May 21, 2019
#2
+22896
+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$$

May 22, 2019