Compute $999^{-1}$ modulo 1000. Express your answer as an integer from 0 to 999.
+118667 Compute the inverse of 999 modulo 1000. Express your answer as an integer from 0 to 999.
999*-1 = 1000*-1+1
So the inverse is -1
but you want an integer from 0 to 999 so
1000-1 = 999
the inverse of 999 mod 1000 is 999
check
999*999=998001 = 1 (mod1000)
+26387 Compute \(999^{-1} \pmod{1000}\).
Express your answer as an integer from 0 to 999.
Modular multiplicative inverse using Euler's theorem
\(\small{ \begin{array}{|rcll|} \hline && 999^{-1} \pmod{1000} \\ &\equiv& \dfrac{1}{999} \pmod{1000} \quad & | \quad \gcd(1000,999)=1! \\ &\equiv& 999^{\phi(1000)-1} \pmod{1000} \quad & | \quad 999 \equiv -1 \pmod{1000} \\ &\equiv& (-1)^{\phi(1000)-1} \pmod{1000} \quad & | \quad \phi(1000) = 400~\text{ (Euler torent function)} \\ &\equiv& (-1)^{400-1} \pmod{1000} \\ &\equiv& (-1)^{399} \pmod{1000} \\ &\equiv& -1 \pmod{1000} \\ &\equiv& -1+1000 \pmod{1000} \\ \mathbf{ 999^{-1} \pmod{1000} }&\equiv& \mathbf{ 999 \pmod{1000}} \\ \hline \end{array} }\)
