How to compute 22475mod?
My work:
2^{2475} = 2^{5^2\cdot 9\cdot 11} = 1048576^{5\cdot 9\cdot 11} = (-930)^{5\cdot 9\cdot 11} \bmod 9901
but I got stuck after this. Any further computation continuing from where I got stuck results in numbers that are too large for me to work with.
Answer
9901 is prime and 9900=4\cdot2475 then (2^{2475})^4=2^{9900}\equiv 1\pmod{9901} Hence we can solve in the field \Bbb F_{9901} the equation X^4=1 Wolfram gives X=1000,X=8901,X=9900 and we have to pick \color{red}{X=1000} because it corresponds to 2^{2475}.
No comments:
Post a Comment