Determine the order of 3 modulo 100. Hence, or otherwise, find the last two digits of $3^{1001}$.
Since $\gcd(3,100)=1$, Euler's Theorem tells us $3^{\phi(100)} \equiv 1 \pmod {100}$. This means the order is a factor of $\phi(100)=40$. These factors are 1, 2, 4, 5, 8, 10, 20, and 40, and these factors are the only ones we need to test.
The following calculations show $3^{20} \equiv 1 \pmod {100}$.
| n | 3^n | 3^n mod 100 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 81 |
| 5 | 243 | 43 |
| 8 | 6561 | 61 |
| 10 | 59049 | 49 |
| 20 | 3486784401 | 1 |
The order of 3 modulo 100 is 20.
Noting that $1001 = (20 \times 50) + 1$, we proceed as follows
$$ \begin{align} 3^{1001} & \equiv (3^{20})^{50} \times 3 \pmod {100} \\ \\ & \equiv (1)^{50} \times 3 \pmod {100} \\ \\ & \equiv 3 \pmod {100} \end{align}$$
So the last two digits of $3^{1001}$ are 03.