<s>[INST] Sum of 4th powers modulo 125 I have been trying to evaluate $\sum_{i=1}^{125} i^4\pmod {125}$. My attempt has been somewhat like this so far:
We know that 125 has a primitive root. Let's call it $r$. Now we know that $$r,r^2,\ldots, r^{\phi(125)}$$
is actually congruent to the set of positive integers that are less than 125 and relatively prime to it, i.e. all the numbers not divisible by 5. Also note that $\phi(125)=100$. Thus I write the sum as follows:
$$\sum_{i=1}^{125} i^4=(5^4+10^4+15^4+\ldots + 125 ^4)+(1+2^4+3^4+\ldots+124^4)$$
$$=5^4(1+2^4+3^4+\ldots+25^4)+(1+r^4+r^8+\ldots+r^{396})$$
$$\equiv \frac{r^{400}-1}{r^4-1}\pmod {125}$$
$$\equiv 0\pmod {125}$$
But when I calculate the expression using wolphram alpha, I get the answer is 100. Where am I going wrong? Please point out. Thanks in advance. 
 [/INST] As $2^2\equiv-1\pmod5,2$ is a primitive root of $5$
Now from Order of numbers modulo $p^2$
ord$_{5^2}2=4$ or $4\cdot5 $
Now as $2^4\not\equiv1\pmod{25},$ord$_{5^2}2=4\cdot5=\phi(25)$ 
So, $2$ is a primitive root of $5^2$
Using If $g$ is a primitive root of $p^2$ where $p$ is an odd prime, why is $g$ a primitive root of $p^k$ for any $k \geq 1$?, 
$2$ is a primitive root of $5^n, n\ge1$
Now $$\sum_{n=0}^{99}2^{4n}=\dfrac{16^{100}-1}{16-1}$$
Now $16^{100}\equiv?\pmod{125(16-1)}$
Now as $125\cdot15=5^4\cdot3, \displaystyle16^{100}=(1+15)^{100}\equiv1+\binom{100}115+\binom{100}215^2\pmod{5^4\cdot3}$
As $\displaystyle(15^2,125\cdot15)=75,\binom{100}2\equiv0\pmod{25}$
$\displaystyle\implies16^{100}-1\equiv1500\pmod{125\cdot15}$
$\displaystyle\implies\dfrac{16^{100}-1}{16-1}\equiv\dfrac{1500}{16-1}\pmod{125}$
</s>