Factorization and modular inverses

70 Views Asked by At

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$?

2

There are 2 best solutions below

0
On BEST 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}$$

0
On

Not sure about the confusion

as $$-24\cdot2=-48\equiv1\pmod7\iff(24)^{-1}\equiv2$$

and as $8\equiv1\pmod7, $$$(-24)^{-1}\equiv(-24)^{-1}8\pmod7\equiv(-3)^{-1}\equiv2$$

as $-3\cdot2=-6\equiv1\pmod7$