2010/050) Prove that the last 6 digits of 7^10000 is 000001

we know 7^4 = 2401

so 7^10000 = (2401)^2500

now 2401^2500 = (2400+1)^2500

if we collect nth term it it (2500 C n) (2400)^n

for n > 2 2400^n is divisible by 10^6

so we need to look for n = 2 and n =1

n=0 gives 1 and 1-1 = 0

n = 2 => (2500C2)(2400)^2 = 2500*1200*2400 so 10^6 is a factor
n =1 =>(2500)(2400) = 6000000 so 10^6 is a factor

so all the elements except last that is 1 is divisible by 10^6 and last element is 1

so last 6 digits are 000001 or 7^10000 mod 10^6 = 1