If 2^33 is divided by 17 then remainder will be _____

Question

If 2³³ is divided by 17 then find remainder without doing division.

 

Answer 1

Using Fermat's theorem.

17 is a prime number.

Fermat's theorem states that
for any prime number p, we have
a^p-1 = 1 mod p

So, 2^(17-1) = 1 mod 17
=> 2¹⁶ = 1 mod 17
=> (2¹⁶)² = 1² mod 17
=> 2³² = 1 mod 17

=>2³² * 2 = 2*1 mod 17
=>2³³ = 2 mod 17

Hence, 2 is the right answer.