Thursday, 13 July 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 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

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