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.