Prove that $1^8+2^8+\cdots+99^8 \equiv 1^4+2^4+\cdots+99^4 \pmod{25}.$ 
Prove that $$1^8+2^8+\cdots+99^8 \equiv 1^4+2^4+\cdots+99^4 \pmod{25}.$$

Attempt:
We can easily show that an eighth power can be expressed as a fourth power since $x^8 = (x^2)^4$. Conversely, by Fermat's Little Theorem, $x^{\phi(25)} = x^{20} \equiv 1 \pmod{25}$ if $\gcd(x,25) = 1$ and thus $x^4 = x \cdot x^3 \equiv x^{21} \cdot x^3 \equiv x^{24} \equiv (x^3)^8 \pmod{25}$. $\square$
I am not sure if the above proves the result, but it does show that if we have an $8$th power of an integer modulo $25$ and it is relatively prime to $25$, then it is equal to a fourth power of an integer modulo $25$ and vice-versa. Does that therefore mean they are equivalent?
 A: $\mathbb{Z}/(25\mathbb{Z})^*$ is a cyclic group generated by $2$, hence
$$ \sum_{\substack{1\leq n \leq 25\\ 5\nmid n}}n^4 \equiv \sum_{r=1}^{20}2^{4r}\equiv \frac{16^{24}-16^4}{16-1}\equiv 20\pmod{25} $$
and
$$ \sum_{\substack{1\leq n \leq 25\\ 5\nmid n}}n^8 \equiv \sum_{r=1}^{20}2^{8r}\equiv \frac{256^{168}-256^8}{256-1}\equiv 20\pmod{25} $$
prove our claim. 
To compute $2^N\pmod{125}$ is not difficult since $2$ is a generator of $\mathbb{Z}/(125\mathbb{Z})^*$, too.
A: If $\gcd(x, 25) \neq 1$, then $x$ is a multiple of $5$, so $x^4$ and $x^8$ are multiples of $25$ and don't contribute to the sum. Thus, we will focus on the cases where $\gcd(x, 25)=1$.
Also, $x \equiv x+25 \pmod{25}$, so we really have the following:
$$4(1^4+2^4+3^4+[...]+24^4) \equiv 4(1^8+2^8+3^8+[...]+24^8) \pmod{25}$$
Now, your work shows that there is a bijective mapping between the fourth powers of the group of units $25$ and the eighth powers of the group of unts of $25$, so for any fourth power on the left side, we can find an eighth power on the right side and then subtract the two from both sides. We can do this repeatedly until we've subtracted all of the powers and gotten to $0 \equiv 0 \pmod{25}$, concluding the proof.
A: $100 = 2^2 \times 5^2$. It suffices to show that the two sums are equal mod $4$ and mod $25$.
If $x$ is even, $x^4 \equiv x^8 \equiv 0 \mod 2^2$, while if $x$ is odd,
$x^4 \equiv x^8 \equiv 1 \mod 2^2$.  So $\sum_{i=1}^{99} x^4 \equiv \sum_{i=1}^{99} x^8 \mod 2^2$.
Similarly, if $x$ is divisible by $5$, $x^4 \equiv x^8 \equiv 0 \mod 5^2$.
On the other hand, the multiplicative group $U$ of units in $\mathbb Z / 25 \mathbb Z$ (i.e. the numbers mod $25$ that are not divisible by $5$) is cyclic of order $\phi(5^2) = 20$.  The maps $t \to t^4$ and $t \to t^8$ are homomorphisms of this group, with the same range (namely the $5$ elements $y$ such that $y^5 = 1$).  Thus $x^4$ for $x \in U$ and $x^8$ for $x \in U$ run over this same set, each element occurring $4$ times.  If we take the 
numbers from $1$ to $99$ not divisible by $5$, each element occurs $20$ times.  Thus the two sums mod $25$ are the same.
EDIT:  Somewhat more generally, $\sum_{x=1}^{N-1} x^4 \equiv \sum_{x=1}^{N-1} x^8 \mod N$ for all positive integers $N$.  One way to see this is that
$$ \sum_{x=1}^{N-1} (x^8 - x^4) = \dfrac{N\; (2\,{N}^{8}-9\,{N}^{7}+12\,{N}^{6}-12\,{N}^{4}+9\,{N}^{3}-2\,{N}^{2})}{18}$$ and $2\,{N}^{8}-9\,{N}^{7}+12\,{N}^{6}-12\,{N}^{4}+9\,{N}^{3}-2\,{N}^{2} \equiv 0 \mod 18$ for all $N$.
A: We only need to prove that
$$(5a+1)^8 + (5a+2)^8 + (5a+3)^8 +(5a+4)^8 \equiv_{25} (5a+1)^4+(5a+2)^4+(5a+3)^4+ (5a+4)^4$$
In this equations the elements of the polynomials that only matter are the elements of the form $\dbinom{8}{i}(5a)^ik^{8-i}$ with $i=0,1$, because for $i>1$, the number is $\equiv_{25} 0$. This is the same for the right side, only matters $\dbinom{4}{i}(5a)^ik^{4-i}$ with $i=0,1$. So let's check the rest of the equation and reduce it using this idea:
$$(5a+1)^8 + (5a+2)^8 + (5a+3)^8 +(5a+4)^8 -(5a+1)^4-(5a+2)^4-(5a+3)^4- (5a+4)^4 \equiv_{25} 0$$
$$\Leftrightarrow (8*5a*1+1) + (8*5a*2+2^8) + (8*5a*3+3^8) +(8*5a*4+4^8) -(4*5a*1+1^4)-(4*5a*2+2^4)-(4*5a*3+3^4)- (4*5a*4+4^4) \equiv 0$$
And using the mod 25, we get:
$$\Leftrightarrow (40a+1) + (20a+6) + (5a+11) +(10a+11) -(20a+1)-(10a+16)-(15a+6)- (5a+6) \equiv_{25} a((40+20+5+10)-(20+10+15+5))+(1+6+11+11-1-16-6-6) \equiv 29-29 \equiv 0$$
So it's done. Now, in the case of the number 99, you can divide the space in sets of 5 consecutive numbers as here: 
$$\{1,2,3,4,5\}, \{6,7,8,9,10\},\dots ,\{96, 97, 98, 99 \}$$
and as the numbers of the form $5k$ are $\equiv_{25}0$ when they're at 4th power, the other ones fulfil the identity.
