0
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ $$512\equiv?\pmod{61}$$ $\endgroup$ – lab bhattacharjee Dec 1 '16 at 17:56
  • $\begingroup$ 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)\ \ $ $\endgroup$ – Bill Dubuque Dec 1 '16 at 18:32
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\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.