* Andy Latto <andy.latto@pobox.com> [Mar 13. 2012 19:47]:
[...]
Maple? Mathematica? Continued Fractions? This is something you can calculate in your head in under 2 minutes. Use the Chinese Remainder Theorem.
25^1312000 = 0 mod 5.
25^1312000 = 1 mod 128, since 1312000 is a multiple of 32. (you might think that the exponent of (Z/Z128)* was 64, since it has 64 elements. But since (Z/8Z)* has exponent 2 (3^2 = 9 = 1 mod 8 is the only case you need to check, since the other elements are 1, -1, and -3), (Z/128Z) has exponent 32.
(To see that 1312000 is a multiple of 32, you just need to verify that 1312 is a multiple of 4, which follows from the fact that 12 and 100 are multiples of 4).
So to compute 25^1312000 mod 640, we just need to find a number mod 640 that is 0 mod 5 and 1 mod 128. 128 = 3 mod 5, and 3 * 3 + 1 = 10 = 0 mod 5, so the solution is (128 * 3) + 1 = 385.
Andy
And the winner is: brain.