Number Theory

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)

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} }$