As described on Wikipedia:
abmodn=((amodn)(b−1modn))modn
When I apply this formula to the case (1023/3)mod7:
\begin{align*} (1023/3) \bmod 7 &= \left((1023 \bmod 7)((1/3) \bmod 7)\right) \bmod 7 \\ &= ( 1 \cdot (1/3)) \mod 7 \\ &= ( 1/3) \mod 7 \\ &= 1/3 \end{align*}
However, the real answer should be (341) \bmod 7 = \mathbf{5}.
What am I missing? How do you find (a/b) \bmod n correctly?
Answer
\frac{1}{3}\mod 7 = 3^{-1}\mod 7
You need to solve below for finding 3^{-1}\mod 7 : 3x\equiv 1\pmod 7
Find an integer x that satisfies the above congruence
No comments:
Post a Comment