0
$\begingroup$

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Do you know "Fermat's little theorem"? It will take you very quickly to the answer. $\endgroup$ – Doug M Jun 9 '16 at 18:14
  • 3
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Jun 9 '16 at 18:17
2
$\begingroup$

Working modulo 13:

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.