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?
 A: Calculate $3^2, 3^3, 3^4, 3^5, 3^6, 3^7$ modulo $99$, i.e. reduce at each step.  For example $3^4=729\equiv 36\pmod{ 99}$.  Now $3^5=3\cdot 3^4\equiv 3\cdot 36\equiv 45$.  You will find that $$9=3^2\equiv 3^7\pmod{99}$$
Hence $$3^{2+5k}\equiv 9\pmod{99}$$
for all $k\in \mathbb{Z}^{\ge 0}$. Hopefully you can finish the problem from here.
A: Note that $3^n$ is divisible by $9$ for $n\ge 2$ so the outcome will be $0, 9, 18, 27, \dots 90$ - eleven different answers, which have different residues modulo $11$.
Now by little Fermat $3^{10}\equiv 1$ mod $11$, so that $3^{2003}\equiv 3^3=27 \equiv 5$ mod $11$.
I will leave you to work out the final answer.
A: 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.
A: As $(3^{2003},99)=9,$
we can start with $3^{2003}/9\pmod{99/9}$ i.e., $3^{2001}\pmod{11}$
As $(3,11)=1,$ using Fermat's Little Theorem, $3^{10}\equiv1\pmod{11}$ and $2001\equiv1\pmod{10}$
$\implies3^{2001}\equiv3^1\pmod{11}$
Using property$\#9$ of this,  $9\cdot3^{2001}\equiv9\cdot3^1\pmod{9\cdot11}\equiv?$
