# Fermat's Little Theorem $8^{123}$ modulo ${61}$

Using Fermat's Little Theorem, find the least residue of $8^{123}$ modulo $61$

I've started with:

$8^{60}\equiv 1 \pmod{61}$

$8^{120}\equiv (8^{60})^2\equiv 1^2 \equiv 1 \pmod{61}$

So: $8^{2 \cdot 60+3} \equiv (8^{60})^2 \cdot 8^3 \equiv 1^2 \cdot 512 \pmod{61}$

Very stuck what to do from here!

• $$512\equiv?\pmod{61}$$ – lab bhattacharjee Dec 1 '16 at 17:56
• You're almost done. An easy way to finish is: $\ {\rm mod}\ 61\!:\ 8^3 \equiv 8(\color{#c00}{8^2})\equiv 8(\color{#c00}3)\ \$ – Bill Dubuque Dec 1 '16 at 18:32

## 3 Answers

$$8^3 \equiv 8 \cdot 64 \equiv 8 \cdot 3 \equiv 24.$$

First get the remainder $3\equiv 123 \pmod{\varphi(61)} \equiv 123 \pmod{60}$

Now the result to your question is: $24\equiv 8^{3} \pmod{61}$

(mod 61): $$8^{123} = 2^{369} = 2^9 = 2^6 2^3 = 3 \cdot 2^3 = 24$$