What is the reminder when 21000 is divided by 13Solution2100

What is the reminder when 2^1000 is divided by 13?

2^1000 divided by 13

Lets take 2^6, which is 64

64 = -1 (mod 13)

So, split 2^1000 as : 2^996 * 2^4

Since 2^6 = -1 mod 13

(2^996), i.e (2^6)^166 will be (-1)^166 ---> 1 mod 13

So far we have found that 2^996 when divided by 13 leaves remainder of 1...

We have 2^4 still left over

2^4 ---> 16

16 = 3 mod 13

So, 2^(1000) mod 13 = 1 * 3 ---> 3 mod(13)

So, answer ---> 3