Find the least residue of 75 modulo 50 without using a calcu

Find the least residue of 7^5 modulo 50 without using a calculator, and using mi efficient method. Make sure that your solution shows the method that you used. using Fermat\'s little theorem, find the least residue of 8^123 modulo 61.

Solution

a)

7^2=49=-1 modulo 50

7^4=(7^2)^2=(-1)^2=1 modulo 50

7^5=7*7^4=7*1=7 modulo 50

b)

gcd(8,61)=1

61 is prime so by Fermat\'s Little theorem

8^{61-1}=1 mod 61

8^{60}=1 mod 61

So,

(8^{60})^2=8^{120}=1 mod 61

8^2=64=3 mod 61

8^3=8^2*8=3*8=24 mod 61

Hence

8^{123}=8^{120}**^3=24 mod 61