Wednesday, 15 July 2015

elementary number theory - How to compute 22475bmod9901?



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

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