Determine the last two digits of $13^{1000}$.
We remind ourselves of Euler's Theorm (5.14), which states that for $n>1$ and $\gcd(n.a)=1$, then
$$ a^{\phi(n)} \equiv 1 \pmod n $$
Since $\gcd(13, 100)=1$ we have
$$ 13^{\phi(100)} \equiv 1 \pmod {100} $$
We have $\phi(100)=40$, and so
$$ 13^{40} \equiv 1 \pmod {100} $$
Noting that $1000 = 40*25$, we have
$$ \begin{align} 13^{1000} & \equiv (13^{40})^{25} \pmod {100} \\ \\ & \equiv 1^{25} \pmod {100} \\ \\ & \equiv 1 \pmod {100} \end{align} $$
So the last two digits of $13^{1000}$ are $01$.