Find the remainder if $19^{55}$ is divided by 13.

Question

The question, as stated in the title, is

Find the remainder if $19^{55}$ is divided by 13.

Here is my approach for solving this problem.

I know that $19\equiv6$ (mod 13), so $19^{55}\equiv 6^{55}$ (mod 13). Then I can see that $6^{12}\equiv 1$ (Fermat's Little Theorem), so $6^{55}=\left(6^{12}\right)^46^7\equiv 6^7$ (mod 13).

And from here I don't know where to go. Could you give me a bit of guidance? Is there a much easier path to the answer?

Answer 1

Very good job so far and you were already very close.

Observe that $\;6^{12}=1\pmod {13}\implies 6^6=1\;\;or\;\;-1\pmod{13}\;$ , so

$$6^2=10=-3\pmod{13}\implies 6^3=(-3)\cdot6=-18=-5=8\pmod{13}$$

and thus finally

$$6^6=\left(6^3\right)^2=8^2=64=-1\pmod{13}$$

End now your exercise.

Answer 2

$6^7\equiv 6(6^2)^3\pmod{13}\equiv 6(-3)^3\pmod{13}\equiv -6.27\pmod{13}$

Answer 3

Your answer $6^7 \pmod{13}$ reduces to $7$, which is the remainder. Since $55$ factors into $5 \cdot 11$, I took $19^5 \pmod{13}$ which reduces to $2$. Therefore $19^{55} \pmod{13}$ is $2^{11} \pmod{13}$ reduces to $7$, which is the remainder.