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. 
 A: There is not much number theory needed to evaluate this sum. Note that
$$\sum_{i=0}^{125}i^4 = \sum_{i=0}^4\sum_{j=0}^4\sum _{k=0}^4(25i+5j+k)^4$$
Now we apply the binomial formula to 
$$(5(5i+j)+k)^4$$
and get
$$5^4(5i+j)^4+{4\choose1}5^3(5i+j)^3k+{4\choose2}5^2(5i+j)^2k^2+{4\choose3}5(5i+j)k^3+k^4$$
The 1st term is $0\pmod{125}$ and if we sum over $k$ the 2nd, 3rd and 4th term vanishes, too, because
$$\sum_{k=0}^4 k=2\cdot 5$$
$$\sum_{k=0}^4 k^2 =6\cdot 5$$
$$\sum_{k=0}^4 k^3 =4\cdot 5^2$$
so only
$$\sum_{i=0}^4\sum_{j=0}^4\sum _{k=0}^4k^4$$
remains and is 
$$\sum_{i=0}^4 1 \sum_{j=0}^4 1 \sum_{i=0}^4 k^3\equiv100\pmod{125}$$
A: The problem in your attempt is that $r^4-1$ is divisible by five, and division by five is not well defined in the ring of residue classes modulo $125$. For example $125/5$ and $0/5$ are not congruent modulo $125$ even though $125$ and $0$ are. Therefore your sum formula is not valid. Do observe that the error will be a multiple of $25$ (because $\gcd(125,r^4-1)=5$ and $125/5=25$). This fits with the result you got from WA!
Instead, you should notice that:


*

*If $i\equiv0\pmod5$, then $i^4\equiv0\pmod{125}$, and you can leave those terms out of the reckoning (you already did, actually).

*In the cyclic group $G=\Bbb{Z}_{125}^*$ of order $100$, the fourth powers form a unique subgroup $H$ of index four (this happens in all cyclic groups of order divisible by four). We can easily identify that the subgroup consisting of residue classes of integers $\equiv1\pmod5$ is also such a subgroup, so
$$H=\{\overline{a}\in\Bbb{Z}_{125}\mid a\equiv1\pmod5\}.$$

*Raising to fourth power is a 4-to-1 mapping in $G$, implying (by basic properties of homomorphisms) that each element of $H$ is attained as $i^4$ exactly four times.

*Therefore your task is to calculate the sum
$$
\sum_{i=1}^{125}i^4\equiv4\sum_{x\in H}x=4\sum_{i=1, i\equiv1\pmod5}^{125}i.
$$
This is the sum of an arithmetic progression, and I'm sure you can manage. You can calculate it as an integer, and then reduce modulo $125$.

A: 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}$
