What is the remainder of $$$2^{125}$$ divided by 13?
A 2 B 4 C 6 D 8 E 10
Division problem
Re: Division problem
Use Fermat's Little Theorem. The answer should be C. 6.
The theorem is 2^(n-1)=1 mod n.
So 2^(12)=1 mod 13.
Now 2^125=2^(12*10)*2^(5)=2^(5)=32=6 mod 13.
The theorem is 2^(n-1)=1 mod n.
So 2^(12)=1 mod 13.
Now 2^125=2^(12*10)*2^(5)=2^(5)=32=6 mod 13.