find last 3 digit of sum (9^k) k = 1 to 400

the sum is S = [1<= n <= 400] 9^n

we have 1000 = 8 * 125 so to compute S mod 8 and S Mod 125

now 9 = 1 mod 8 so 9^n = 1 mod 8

there are 400 numbers each is 1 mod 8 so sum = 0 mod 8

sum = 9/8(9^400-1)

as 9 and 125 are coprime as per http://www.cut-the-knot.org/blue/Euler.s…

9^φ(125) mod 125 = 1

now 125 = 5^3 so φ(125) = 125(1-1/5) = 100

so 9^(100) = 1 mod 125
or 9^400 = 1 mod 125
so 9/8(9^400-1) = 0 mod 125

now S = 0 mod 8 and S = 0 mod 125 and

hence S = 0 mod 1000 so last 3 digits are zero