Krdytkyu

So I'm trying to prove the following:
For any 5 ints, if the sum of the numbers (each raised to the power of 5) is divisible by 25 then the product of those original 5 ints is divisible by 5.

What I did first was notice that any integer raised to the power of 5 is congruent to 0,1,7,18 or 24 mod 25. And if we choose 5 numbers, and the sum of these powers of 5 is divisible by 25, then it seems like 0 must be one of those 5 numbers (It doesn't seem like any 5 numbers as a combination of 1,7,18,24 summed would be divisible by 25) But if we choose 0 as one of the 5 numbers, it'll work. Then if must always include a 0 for the sum to be divisible by 25, then the product will be divisible by 5 since the product will be 0.

That's what I noticed but I don't know how to prove this. Any advice?

You are basically done already. You just have to write out your argument in detail as for why it is the case that the only way to get back $0bmod 25$ from the sum of five fifth powers is to have one of those powers be congruent to $0bmod 25$.

If this is for your own edification, you could simply exhaust over the possible sums that exclude $0bmod 25$ (there are 1024 such sums if you naively count them, but if you are really careful there are only 56 important cases). If you don't want to do that, you could make a series of arguments like the following...

The only residues $bmod 25$ that are fifth powers are $0,pm 1$, and $pm 7$. If exactly one of the five numbers in the sum has a residue of $7$ and no numbers have a residue of $-7$, then the entire sum can only be $3,4,5,6,7,8,9,10$, or $11bmod 25$. The same argument applies to the case of exactly one number having residue $-7$ and no numbers of residue $7$. Similar arguments will handle sums in which there are only $7$'s or $-7$'s. So the only way to get back $0bmod 25$ is to have a mixture of $7$'s and $-7$'s. Now keep on handling cases...

While this is much less effort than enumerating all possible sums, you can see that the entire argument will still be long and boring. Is there a more clever way? I hope so, but it is late, and I can't think very well.

At the end, you will see that the only sums that work are those that have at least one number with a residue of $0bmod 25$. But wait, which numbers have fifth powers that are congruent to $0$? Those that are divisible by 5. Thus, when you do to take the product of the terms in your sum, it too will be divisible by $5$.

What you have written is correct. More precisely, the fifth power of every number is congruent to one of $0, pm 1 , pm 7$ modulo $25$. To show this, one sees that $(a+5)^5 equiv a^5 mod 25$ for all $a$, and then checks $a^5 mod 25$ for $a = 0,pm 1 , pm 2$.

However, if $a^5+b^5+c^5+d^5+e^5 equiv 0 mod 25$, then this is equivalent to the statement that the sum of five (possibly repeated) elements of ${0,pm 1, pm 7}$ is a multiple of $25$.

It is easy to see that this cannot happen with just the sets ${pm 1}$ and ${pm 7}$. For example, the sum of five elements from ${pm 1}$ must be odd, and have absolute value smaller than $6$, so cannot be a multiple of $25$. Similarly, the sum of $5$ elements from ${pm 7}$ must be odd, a multiple of $7$ and have absolute value smaller than $36$, so is not a multiple of $25$.

For the combined set ${pm 1,pm 7}$, again the sum of any five elements must be odd. However, $25$ is of the form $7 times 3 + 4 = 7times 4 - 3$. Therefore, there must at least be three elements of absolute value $1$, otherwise the sum will be of the form $7npm b$ where $|b| leq 2$, which cannot equal to $25$. However, since we have only $5$ elements to choose, the absolute value of a sum consisting of at least three elements of absolute value $1$, cannot exceed absolute value of $18$. Hence, no such sum is a multiple of $25$.

Which tells us, that $0$ must be the remainder when one of the $x^5$ is divided by $5$. Or, such an $x$ is a multiple of $5$.