Monday, February 20, 2017

elementary number theory - How to compute $2^{2475} bmod 9901$?


How to compute $2^{2475} \bmod 9901$?


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

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