Question

Using fermats little theorm, find the least residue of 8^123 modulo 61

Answer 1

Fermat's little theorem says
if p is prime, and p does not divide a, then
a^(p-1)≡1 mod p.

Here we put p=61, therefore 61 does not divide a=8.
Hence 8^(61-1)≡1 (mod 61), or
8^(60)≡1 (mod 61).

Recall the multiplication rule of modulus arithmetic,
8^120≡8^60 × 8^60 ≡1×1≡1 (mod 61).

We conclude therefore
8^123≡8^3*8^60*8^60≡8^3*1*1≡8^3 (mod 61)

Can you find 8^3 (mod 61) ?