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**