Thursday, May 25, 2017

How to apply modular division correctly?




As described on Wikipedia:
abmodn=((amodn)(b1modn))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

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...