Saturday, 18 July 2015

How to apply modular division correctly?




As described on Wikipedia:
abmod



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

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}...