Tuesday, 14 June 2016

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 81(mod7)) 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)11(modp)
6[4(24)1]1(modp).



So we have 614(24)1. Similarly, we have (2)112(24)1. Therefore, we have



(24)1+61+(2)1(24)1(14+12)9(24)1



No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...