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 \)
Do you see the Pascal's triangle ?
