Given $a,b$ positive integers, and $b$ odd, find $\left( 1^b+2^b+\cdots +a^b \right) \mod a$.
Here is my thought process:
For $1^b+2^b+\cdots +a^b$, it is obvious that $a^b \equiv 0 \mod a$.
Then, $(a-1)^b \equiv (-1)^b \equiv -(1^b) \mod a$, as b is odd.
Similarly, $(a-2)^b \equiv (-2)^b \equiv -(2^b) \mod a$, and so on.
We see that $1^b +(a-1)^b \equiv 0 \mod a, 2^b + (a-2)^b \equiv 0 \mod a, \cdots$
So, if $a$ is odd, then all $a-1$ terms will sum to be equivalent to $0 \mod a$.
If $a$ is even, then we take the middle term, $x=\frac{a}{2}$, and calculate $x^b \mod a$.
If $x$ is even, then $x=2y$ for some $y$, and $x^b \equiv 2^b y^b \equiv 0 \mod (4y=2x=a)$ for $b>2$
If $x$ is odd, then $x=2y+1$ for some $y$, and $x^b \equiv (2y+1)^b \equiv 2y(2y+1)^{b-1}+(2y+1)^{b-1} \equiv (2y+1)^{b-1} \mod (a=2x=4y+2) \equiv \cdots \equiv 2y+1 \mod a \equiv x \mod a$
So, $\left( 1^b+2^b+\cdots +a^b \right) \equiv 0$ or $\frac{a}{2} \mod a$
Is this correct?