+0  
 
0
77
2
avatar

Compute $999^{-1}$ modulo 1000. Express your answer as an integer from 0 to 999.

 May 28, 2021
 #1
avatar+114069 
+1

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)

 May 28, 2021
 #2
avatar+26135 
+2

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} }\)

 

laugh

 May 28, 2021

9 Online Users