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?

Since 2006 = 2 * 17 * 59, we can calculate 61^2006 modulos 2, 17, and 59, and then put the pieces together again.

Clearly 61^2006 = 1 (mod 2).

Consider 61^2006 = 10^2006 (mod 17).
By Fermat's Little Theorem, 10^16 = 1 (mod 17).
Since 2006 = 6 (mod 16), 10^2006 = 10^6 = 9 (mod 17).

Similarly, 61^2006 = 2^2006 (mod 59).
By Fermat's Little Theorem, 2^58 = 1 (mod 59).
Since 2006 = 34 (mod 58), 2^2006 = 2^34 = 27 (mod 59)

Now we must solve simultaneous equations for x:
x = 1 (mod 2),
x = 9 (mod 17),
x = 27 (mod 59).

x = 1 (mod 2) and x = 9 (mod 17) => x = 9 (mod 34), by inspection.

Now consider x = 9 (mod 34) and x = 27 (mod 59).
Let x = 9 + 34t, where t is an integer, so that
9 + 34t = 27 (mod 59), and 34t = 18 (mod 59).
In general, we would solve this by finding the modular inverse of 34 using the Euclidean algorithm, but here we can simplify the equation to
17t = 9 (mod 59). Then multiply by 4:
9t = 36 (mod 59), and so t = 4 (mod 59).

Hence x = 9 + 34(4 + 59u), where u is an integer.
So x = 145 + 2006u.

The Chinese Remainder Theorem tells us this is the unique solution, modulo 2006.

Therefore 61^2006 = 145 (mod 2006).
Edited on August 30, 2006, 8:37 pm

Posted by Nick Hobson on 2006-08-30 20:36:58