Tuesday, November 7, 2017

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

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