<s>[INST] 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?
 [/INST] Euler's Theorem states $a^{\phi (n)} \equiv 1 \left(\mod \, \, n\right)$ if $a \perp n$, or $\gcd(a,n)=1$. Since $\gcd(31,36)=1$, 
\begin{equation}
31^{\phi (36)} = 31^{12} \equiv 1 (\mod\,\,36)
\end{equation}
Then,
\begin{align}
(31^{12})^2 &= 31^{144} \equiv 1 (\mod \, \, 36) \\
31^{144} \cdot (31^{12})^{155}  &= 31^{2004} \equiv 1 (\mod \, \, 36)
\end{align}
So,
\begin{equation}
31^{2008} = 31^{2004} \cdot 31^4 \equiv 1 \cdot 31^4 (\mod \, \, 36)
\end{equation}
But $31 \equiv 31 (\mod \, \, 36) \equiv -5 (\mod \, \, 36)$ so
\begin{equation}
31^2 \equiv (-5)^2 (\mod \, \, 36) \equiv 25 (\mod \, \, 36) \equiv -11 (\mod \, \, 36)
\end{equation} 
and then,
\begin{equation}
31^4 \equiv (-11)^2 (\mod \, \, 36) \equiv 121 (\mod \, \, 36) \equiv 13 (\mod \, \, 36)
\end{equation}
Thus,
\begin{equation}
31^{2008} \equiv 1 \cdot 31^4 (\mod \, \, 36) \equiv 13 (\mod \, \, 36)
\end{equation}
</s>