Sunday, 14 May 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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...