Friday, June 15, 2018

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