Find that $8^{103} \bmod(13)$ using Fermat's Little Theorem

Question

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!

Answer 1

You don't need FLT in this case.

Indeed note that

$$8^{2}= 64\equiv -1 \pmod {13}$$

thus

$$8^{103}\equiv(8^2)^{51}\cdot 8 \equiv(-1)^{51}\cdot 8\equiv -8\equiv5 \pmod {13}$$

Answer 2

Apart from using the fact that $8^2\equiv(-1)\mod13$, you can break down the powers. $$\begin{align}8^7\mod13&\equiv(13-5)^7\mod13\\&\equiv(-5)^7\mod13\\&\equiv(5)^2(5)^2(5)^2(-5)\mod13\\&\equiv(25)(25)(25)(-5)\mod13\\&\equiv(26-1)(26-1)(26-1)(-5)\mod13\\&\equiv(-1)(-1)(-1)(-5)\mod13\\&\equiv\boxed 5\mod13\end{align}$$

Answer 3

$8^{103} \equiv8^7\equiv(8^2)^38\equiv(-1)^38\equiv-8\equiv5(mod 13)$

Answer 4

You have already proved that $ 8^{103} = 8^7 $ mod (13).

Since $8^2 = 64 = 5(13)-1 =-1$ mod (13), we have $ 8^7 =(-1)^3 \times 8= -8$ mod (13).

Therefore the final answer is $ 8^{103} = 5 $ mod (13).

Answer 5

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.