Show how to calculate each of the following quickly without

Show how to calculate each of the following quickly without using a digital device.

(a) 3^49384582934 (mod 11)

(b) 5^258 (mod 7)

(c) 7^24000 (mod 21)

Solution

(a) 3^5 = 243, 243%11 is 1. so 3^49384582934 can be written as (3^49384582930) * (3^4) mod 11 is 1 * 81 mod 11 which is 4.

(b) 5^6 is 15625 mod 7 is 1. so (5^6)^43 mod 7 is 1.

(c) 7^2 mod 21 is 7. So 7^3 (mod 21) is (7^2)*7 mod 21 is same as 7^2 mod 21 is 7 again. Extending this we can see that 7^x is always 7. So 7^24000 (mod 21) is 7.