EXERCISE:
Find $8^{103} \pmod{13}$
SOLUTION:
We have that $p=13$ , $n=8$ , $m=103$
We know (from Fermat’s Little Theorem) that when n is not divided with p,we take that:
$$a^{p-1}=1 \pmod p$$
So,we have that $$8^{12}=1\pmod{13}$$
We have also that $103=8\cdot12+7$.
So, $$8^{103}=(8^{12})^8 \cdot 8^7=8^7\pmod {13}$$
as
$8^{12}=1 \pmod{13}$
From now and then i can't understand how we continue the exercise:
$$
\begin{split}
8^7\bmod(13)
&= (-5)^7\bmod13 \\
&= 5^6\cdot(-5)\bmod13 \\
&= 25^3\cdot(-5)\bmod13 \\
&= (-1)^3\cdot(-5)\pmod{13} \\
& =5\bmod(13)
\end{split}
$$
Can anyone explain me how we we end up with this result?My problem is that i can't understand how to proceed after $8^7\bmod(13)$
I would really appreciate a thorough explanation, since I've just started working on these type of problems using Fermat’s Little Theorem and I have to clear my mind on them.
Thanks in advance!
Best Answer
I would have gone for the $2$'s:
$$8^{103} = 2^{309} \equiv 2^9 \equiv 16\cdot 16 \cdot 2 \equiv 3\cdot 3\cdot2 \equiv 18 \equiv 5 \pmod{13},$$
still using Fermat's Little Theorem.