Thursday, January 31, 2019

discrete mathematics - How to compute $3^{2003}pmod {99}$ by hand?





Compute $3^{2003}\pmod {99}$ by hand?





It can be computed easily by evaluating $3^{2003}$, but it sounds stupid. Is there a way to compute it by hand?


Answer



I would calculate separately modulo $9$ and $11$ and put the pieces together at the end.



Modulo $9$ is trivial, we get $0$.



Note that $3^5\equiv 1\pmod{11}$, so $3^{2000}\equiv 1\pmod{11}$, and therefore $3^{2003}\equiv 3^3\equiv 27\pmod{11}$. This is already congruent to $0$ modulo $9$, so we are finished.


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