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