# Find the last three digits of the expression 2988^678

asked Aug 27, 2014 in TCS 1 flag

This is a tough question.
Last three digits of an expression is nothing but the remainder when we divide the given expression by 1000.
So $\displaystyle\frac{{{{2988}^{678}}}}{{1000}} = \frac{{{{( - 12)}^{678}}}}{{1000}} = \frac{{{{12}^{678}}}}{{1000}}$
We write 1000 as 8 $\times$125. So we separately find the remainders by dividing the given number by 8 and 125.
Given expression is clearly divisible by 8. Also
Euler totient theorem says ${\left[ {\displaystyle\frac{{{a^{\phi (N)}}}}{N}} \right]_{{\mathop{\rm Re}\nolimits} mainder}} = 1$
Here $\phi(N)$ is the number of co primes of a number N. In this case $\phi(125)$ = 100.
So $\displaystyle\frac{{{{\left( {{{12}^{100}}} \right)}^6}{{.12}^{78}}}}{{125}} = \frac{{{1^6}{{.12}^{78}}}}{{125}}$
Now ${12^{78}} = {4^{78}}{.3^{78}} = {(1 + 15)^{39}}.{(10 - 1)^{39}}$
${(1 + 15)^{39}}.{( - 1)^{39}}{(1 - 10)^{39}}$
- ($1 + {}^{39}{C_1}.15 + {}^{39}{C_2}{.15^2}....$ ). ($1 + {}^{39}{C_1}.10 + {}^{39}{C_2}{.10^2} - {}^{39}{C_3}{.10^3}....$
If you observe clearly, ${15^3}$ and ${10^3}$ are 15 multiples. So we can omit the remaining terms.
-(1+39.15 + 39.19.${15^2}$ ).(1-39.10 + 39.19.${10^2}$)
By writing 39 as 40-1 we can simplify this equation fast.
-(1+(40-1).15 + (40-1).19.${15^2}$).(1-390 + (40-1).19.100
-(1+100 - 15 - 19.${15^2}$ ).(1-140 - 19.100)
-(101 - 15 - (20-1).${15^2}$).(1-140+100)
-(101-15+100).(-39)
-(61).39
-2379 = 4
So the remainder is 4.
The original expression is in the format of N = 8K = 125 L + 4
The minimum number satisfies this condition is L = 4.
So 125 (4) + 4 = 504