Determine the remainder when 61²⁰⁰⁶ is divided by 2006.

Can you do this in a short time using pen and paper, and eventually a hand calculator, but no computer programs?

I scratched my head a lot and finally concluded that there is a straightforward way, somewhat lengthy, to solve this.  The fundamental principles of arithmetic mod 2006 will need to be exploited numerous times.  Note that 2006^2 is around 4 million and is therefore well within calculator range.  Reducing mod 2006 while performing a frequently-used algorithm for raising to a large power are the keys -- think binary.

BTW, the answer is 145.

Posted by Richard on 2006-07-27 13:54:30