Page 1 of 1

Division problem

Posted: Thu Dec 16, 2010 8:24 pm
by brain
What is the remainder of $$$2^{125}$$ divided by 13?

A 2 B 4 C 6 D 8 E 10

Re: Division problem

Posted: Fri Dec 17, 2010 12:34 am
by mdornbos
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.

Re: Division problem

Posted: Fri Dec 17, 2010 8:12 am
by brain
Thanks.