What is the remainder of $31^{2008}$ divided by $36$?

Question

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?

Answer 1

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}

Answer 2

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}$.