What is the remainder of $31^{2008}$ divided by $36$? What is the remainder of $31^{2008}$ divided by $36$?
Using Euler's theorem, we have:
$$
\begin{align*}
\gcd(31,36) = 1 &\implies 31^{35} \equiv 1 \pmod{36} \\
&\implies 31^{2008} \equiv 31^{35(57) + 13} \equiv (31^{35})^{57+13} \equiv 1^{57}*31^{13} \\
&\implies 31^{13} \equiv 31\pmod{36}
\end{align*}
$$
So the remainder is $31$, is this correct?

The line that goes $31^{35}\equiv 1 \pmod {36}$ is false. Euler's theorem says that $31^{\phi(n)}\equiv 1 \pmod {36}$, but $\phi(36) = 12$. So we would say $31^{2008} \equiv 31^{4} \pmod{36}$ using the same reduction method (taking away multiples of 12) to get $13 \pmod{36}$.
