As described on Wikipedia:
$$\frac{a}{b} \bmod{n} = \left((a \bmod{n})(b^{-1} \bmod n)\right) \bmod n$$
When I apply this formula to the case $(1023/3) \bmod 7$:
$$\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