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