Find the last three digits of 7^{9999}.

Find the last three digits of 7^{9999}.

Approach: Split the modulus 1000 into 8 and 125, reduce the exponent separately using the multiplicative order in each part, then glue the two residues back together.

143. Split 1000 = 8 * 125. Modulo 8, 7^2 = 49 = 1, so 7^{9999} = 7^{odd} = 7. Modulo 125, Euler's theorem gives an exponent period dividing 100, and in fact 7^{10} = 57^2 = 3249 = 124 = -1 mod 125, so the multiplicative order is 20. Reducing 9999 mod 20 leaves 19, and 7^{19} = 7^{20} * 7^{-1} = 7^{-1}, where the modular inverse is 18 because 7 * 18 = 126 = 1 mod 125. So 7^{9999} = 18 mod 125. The Chinese remainder theorem now solves x = 18 + 125k with x = 7 mod 8. Since 125 = 5 and 18 = 2 mod 8, this reads 2 + 5k = 7, so 5k = 5 and k = 1 mod 8, giving x = 143. Checking, 143 = 7 mod 8 and 143 = 18 mod 125.

Follow-up: What are the last three digits of 7^{7^{7}}, and how do you reduce the tower of exponents correctly?

Key concepts: chinese remainder theorem, multiplicative order, euler theorem, modular inverse.