# Find the remainder when $11^{12}$ is divided by $13$. [duplicate]

I am looking for an easier way than mine to solve the problem.

Problem: Find the remainder when $11^{12}$ is divided by $13$.

Here is what I did. I simplify $11^{12}$ mod $13$ = $(–2)^{12}$ mod $13$. Then I don't know how to simply further.

## marked as duplicate by Dietrich Burde, Henrik, Charles, user228113, LeucippusJun 10 '16 at 1:18

• If we do not use Fermat's Theorem, we can note that $(-2)^6=64\equiv -1\pmod{13}$, so $(-2)^{12}\equiv 1\pmod{13}$. – André Nicolas Jun 9 '16 at 18:17
$$11^{12} \equiv (-2)^{12} \equiv \left((-2)^2\right)^6 \equiv 4^6 \equiv 16^3 \equiv 3^3 \equiv 27 \equiv 1 \mod 13$$
Use Euler's theorem. Let's notice that since $13$ is prime then $\varphi(13)=12$, when $\varphi(13)$ is the number of natural numbers $k$ smaller than $13$ such that $gcd(13,k)=1$. According to Euler's theorem, $11^{12} \equiv 1 (\mod 13)$ since $gcd(11,13)=1$.
Since $2^6 = 64 = 65 - 1 = 5 \cdot 13 -1$, we have $$11^{12} \equiv (-2)^{12} = 2^{12} = 64^2 \equiv (-1)^2 = 1 \bmod 13$$