Determine the rightmost three digits of the number $$1^1+2^2+3^3+...+999^{999}+1000^{1000}$$
Solution: consideration of module 8 $$\sum_{k=1}^{1000} k^k\equiv \sum_{r=1}^8 \sum_{k=1}^{125} (8k-8+r)^{8k-8+r} \equiv \sum_{r=1}^8 \sum_{k=1}^{125} r^{8k-8+r}$$
$$\equiv \sum_{r=1,3,5,7} \sum_{k=1}^{125} r^r+\sum_{k=1}^{125} 2^{8k-8+2} \equiv 125(1^1+3^3+5^5+7^7)+4\equiv 4\pmod{8}$$
for module 125 $$\sum_{k=1}^{1000} k^k\equiv \sum_{r=1}^4 \sum_{k=1}^{200} (5k-5+r)^{5k-5+r}$$ $$\equiv \sum_{r=1}^4 \sum_{k=1}^{200} \left(r^{5k-5+r}+5(k-1)(5k-5+r)r^{5k-5+r-1}+25(k-1)^2\binom{5k-5+r}{2} r^{5k-5+r-2}\right)$$ $$\equiv \sum_{r=1}^4 r^{r-2}\sum_{k=1}^{200} \left(r^2+5(k-1)(5k-5+r)r+25(k-1)^2\binom{5k-5+r}{2}\right)r^{5(k-1)}$$ $$\equiv \sum_{r=1}^4 r^{r-2}\sum_{k=1}^{200} \left(r^2+5(k-1)(5k-5+r)r+25(k-1)^2\binom{r}{2}\right)r^{5(k-1)}\pmod{125}$$
$$p(k)=r^2+5(k-1)(5k-5+r)r+25(k-1)^2\binom{r}{2}=r^2+5r(k-1)+25(k-1)^2\left(r+\binom{r}{2}\right)$$
$$\Delta p(k)=5r+25(2k-1)\left(r+\binom{r}{2}\right)$$
$$\Delta^2 p(k)=50\left(r+\binom{r}{2}\right)$$
$$r=1, p(k)=1+5(k-1)+25(k-1)^2,\Delta p(k)=5+25(2k-1)=50k-20 ,\Delta^2 p(k)=50$$
$$\sum_{k=1}^{200} \left(1+5(k-1)+25(k-1)^2\right) \equiv \binom{200}{1}+30\binom{200}{2}+50\binom{200}{3} \equiv 75\pmod{125}$$
$$r\neq 1, f(n)=\frac{r^2+5r(n-1)+25(n-1)^2\left(r+\binom{r}{2}\right)}{r^5-1} -\frac{5r+25(2n-1)\left(r+\binom{r}{2}\right)}{(r^5-1)^2} +\frac{50\left(r+\binom{r}{2}\right)}{(r^5-1)^3}r^5$$
$$f(0)=\frac{r^2-5r+25\left(r+\binom{r}{2}\right)}{r^5-1} -\frac{5r-25\left(r+\binom{r}{2}\right)}{(r^5-1)^2} +\frac{50\left(r+\binom{r}{2}\right)}{(r^5-1)^3}r^5$$
$$f(200)\equiv \frac{r^2-5r+25\left(r+\binom{r}{2}\right)}{r^5-1} -\frac{5r-25\left(r+\binom{r}{2}\right)}{(r^5-1)^2} +\frac{50\left(r+\binom{r}{2}\right)}{(r^5-1)^3}r^5\equiv f(0)\pmod{125}$$
$$r^{1000}\equiv 1\pmod{125}$$
$$\sum_{k=1}^{200}p(k)r^{5(k-1)}\equiv f(200)r^{1000}-f(0)\equiv 0\pmod{125}$$
$$\sum_{k=1}^{1000} k^k\equiv 75+0\equiv 75\pmod{125}$$
conclusion of CRT:
$$\begin{pmatrix}125 & 8\\1 & 0\\0 & 1\end{pmatrix} \rightarrow \begin{pmatrix}-3 & 8\\1 & 0\\-16 & 1\end{pmatrix} \rightarrow \begin{pmatrix}-3 & -1\\1 & 3\\-16 & -47\end{pmatrix}$$
$47\times 8-3\times 125=1$
$47\times 8\times 75-3\times 125\times 4\equiv 26700\equiv 700\pmod{1000}$
Is there any easier solution?
It can have a very simple elementary solution; we consider the last digit of powers:
$1 ≡ 1 \ mod (10)$
$2^2 ≡ 4 \ mod (10)$
$3^3 ≡7 \ mod (10)$
$4^4 ≡6 \ mod (10)$
$5^5 ≡ 5 \ mod (10)$
$6^6 ≡ 6 \ mod (10)$
$7^7 ≡ 3 \ mod (10)$
$8^8 ≡ 6 \ mod (10)$
$9^9 ≡ 9 \ mod (10)$
So we have a series of last digits like:
$1, 4, 7, 6, 5, 6, 3, 6, 9$
And the sum of this series is:
$s_d=(9+1)\frac{9}{2}-8-2 +2\times 6=47$
Similar series, but with different arrangement can be seen for each ten numbers, i.e between 10 and 20, 20 and 30,.. etc. Therefore the total sum from 1 to 100 is:
$47\times 10=470$
For numbers greater than 100 we have:
$(d_1d_2d_3)=d_1\times 100 +d_2 \times 10 + d_3$
$(d_1d_2d_3)^{(100 ≤a ≤1000)} ≡(d_3)^a \ mod (1000)$; $d_3∈\{1, 2, 3, ...9 \}$
That is the last digits of $(d_3)^a $ make similar series.Hence the total sum of last digit from 1 to 1000 is:
$S_d=47\times 100=4700$
Finally the sum of series has following form:
$S= N \times 10^{n>100} + M \times 1000 +4700 ≡ 700 \ mod (1000)$