+0

Help with Module Inverses

0
97
1

What is $$3^{-1}+3^{-2}$$ (mod 25)? Express your answer as an integer from 0-24 inclusive.

Feb 19, 2021

#1
+25658
+2

What is $$3^{-1}+3^{-2} \pmod {25}$$?

My attempt:

$$\begin{array}{|rcll|} \hline && 3^{-1}+3^{-2} \pmod {25} \\ &\equiv& 3^{-1}+3^{-1}3^{-1} \pmod {25} \\ &\mathbf{\equiv}& \mathbf{3^{-1}\left( 1+3^{-1}\right) \pmod {25}} \\ \hline \end{array}$$

$$3^{-1} \pmod {25} = \ ?$$

$$\begin{array}{|rcll|} \hline 3^{-1} \pmod {25} &\equiv& \dfrac{1}{3} \pmod {25} \\ &\equiv& 3^{\phi(25)-1} \pmod {25} \quad | \quad \phi(25)=20 \\ &\equiv& 3^{20-1} \pmod {25} \\ &\equiv& 3^{19} \pmod {25} \\ &\equiv& 3^{3*6+1} \pmod {25} \\ &\equiv& 3^{3*6}*3 \pmod {25} \\ &\equiv& \left(3^3\right)^6*3 \pmod {25} \quad | \quad 3^3 =27 \equiv 2 \pmod{25} \\ &\equiv& 2^6*3 \pmod {25} \\ &\equiv& 192 \pmod {25} \\ \mathbf{3^{-1} \pmod {25}} &\equiv& \mathbf{17 \pmod {25}} \\ \hline \end{array}$$

$$\begin{array}{|rcll|} \hline 3^{-1}+3^{-2} \pmod {25} &\mathbf{\equiv}& \mathbf{3^{-1}\left( 1+3^{-1}\right) \pmod {25}} \quad | \quad \mathbf{3^{-1} \pmod {25}} \equiv \mathbf{17 \pmod {25}} \\ &\equiv& 17 ( 1+17 ) \pmod {25} \\ &\equiv& 17*18 \pmod {25} \\ &\equiv& 306 \pmod {25} \\ \mathbf{3^{-1}+3^{-2} \pmod {25}} &\equiv& \mathbf{6 \pmod {25}} \\ \hline \end{array}$$

Feb 19, 2021