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

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.

• Well, just compute $8^7\pmod {13}$. We have $8^2 = 64\equiv -1\pmod {13}$ so that seriously helps. – lulu Jan 16 '18 at 16:36
• That's right.Thanks! – Paris K. Patsogiannis Jan 16 '18 at 22:53

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

• @ParisK.Patsogiannis note that $-8+13=5$ then $-8\equiv 5 \pmod{13}$ – user Jan 16 '18 at 22:45
• lol i understood it immediately!Thanks,for your answer! – Paris K. Patsogiannis Jan 16 '18 at 22:52
• @ParisK.Patsogiannis You are welcome, Bye! – user Jan 16 '18 at 22:53

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.

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}

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

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