Tuesday, 14 June 2016

elementary number theory - Factorization and modular inverses




In this post in the last method the factorials were factorized. But I don't quite understand how that works.



Lets say we have



$$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$



modulo a prime $p$, for instance $7$. Then $(-24)^{-1} = 2$, $(6)^{-1} = 6$ and $(-2)^{-1} = 3$ (correct me if I'm wrong).
The sum is congruent to $11 \equiv 4$ modulo $7$ which is correct.



However, the factorized method multiplies $(-24)^{-1}$ by $8$ modulo $7$. That is $(-24)^{-1}$ (because $8 \equiv 1 \pmod 7$) which equals $2$.. that is wrong.




Am I doing something wrong here? Is $7$ an exception because $8$ is congruent to $1$?


Answer



I think the problem is a mistake that was pointed out in the comments. Note that



$$-24(-24)^{-1}\equiv1\pmod p$$
$$6[-4(-24)^{-1}]\equiv1\pmod p$$.



So we have $6^{-1}\equiv-4(-24)^{-1}$. Similarly, we have $(-2)^{-1}\equiv12(-24)^{-1}$. Therefore, we have



$$(-24)^{-1}+6^{-1}+(-2)^{-1}\equiv(-24)^{-1}(1-4+12)\equiv9(24)^{-1}$$



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