0
$\begingroup$

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!

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

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

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

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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