Remainder of a sum modulo 211

On the contrary, assume there exists a positive integer $n$ such that $p-1 \not \mid n$ , but $p \mid \sum \limits_{k=0}^{p-1} k^n$ . Let $n$ be the smallest positive integer satisfying this property. We write $n= m \times (p-1) + r$ , where $m \geq 0$ and $0 \leq r < p-1$ by the division algorithm. Then, note that $\sum \limits_{k=0}^{p-1} k^n = \sum \limits_{k=0}^{p-1} k^{ m \times (p-1) + r}$ $= \sum \limits_{k=0}^{p-1} \left ( k^{p-1} \right )^m \times k^r \equiv \sum \limits_{k=0}^{p-1} k^r \pmod{p}$ where the last step follows from Fermat's Little Theorem. This shows that if $n$ satisfies the condition, so does $r$ . Since $n$ is the smallest positive integer satisfying this condition, either $r=0$ or $r=n$ . However, $r=0 \implies p-1 \mid n$ , a contradiction. So we must have $m=0$ , $n=r$ . Also note that this implies $1 \leq n < p-1$ . For all smaller integers $i$ , $p$ must divide $\sum \limits_{k=0}^{p-1} k^i$ . From Pascal's identity, we have $\sum \limits_{k=0}^{n} \binom{n+1}{k} (1^k + 2^k + \cdots + p^k)= (p+1)^{n+1}-1$ $\implies \sum \limits_{k=0}^{n-1} \binom{n+1}{k} (1^k + 2^k + \cdots + p^k) + \binom{n+1}{n} (1^n + 2^n + \cdots + p^n) = (p+1)^{n+1}-1$ Note that $(p+1)^{n+1}-1 \equiv 1 -1 \equiv 0 \pmod{p}$ , and also note that $\sum \limits_{k=0}^{n-1} \binom{n+1}{k} (1^k + 2^k + \cdots + p^k) \equiv 0 \pmod{p}$ . Hence we must have $(n+1)(1^n+2^n+...+ p^n) \equiv 0 \pmod{p}$ . But $p>n+1$ from our previous observation, so $\gcd (n+1, p)= 1$ , implying $p \mid 1^n + 2^n + \cdots + (p-1)^n$ , a contradiction. This proves our claim. QED

The rest of the analysis is trivial. Let $c_{n}$ denote the coefficient of $x^n$ in $(x^3+x+2)^{71}$ . The given sum can be rearranged as $\sum \limits_{n=0}^{71 \times 3} c_n (1^n + 2^n + \cdots + 210^n)$ From our claim, all other terms leave no remainder when divided by $211$ other than $c_{210} \times (1^{210} + 2^{210} + \cdots + 210^{210})$ and $c_{0} \times (1^0 + 2^0 + \cdots + 210^{210})$ By Fermat's Little theorem, $1^{210} + 2^{210} + \cdots + 210^{210} \equiv 1 + 1 + \cdots + 1 \equiv 210 \equiv -1 \pmod{211}$ Again, $c_{0} \times (1^0 + 2^0 + \cdots + 210^{210} ) \equiv c_0 \times (1+1+\cdots + 1) \equiv -c_0 \pmod{211}$ Our desired remainder equals $-1 \times (c_0 + c_{210}) \pmod{211}$ An easy check shows that $c_0 + c_{210} \equiv 142 \pmod{211}$ . Our desired remainder will then be: $-142 \pmod{211} \equiv 69 \pmod{211}$

Frankly no. It is true for sum of first n 1st,2nd and 3rd powers (evident from the formulas), if n+1 is a prime number. And I just extrapolated it to all integer powers. For odd powers it is obvious because the remainders from a^n and (211-a)^n will cancel. But for even powers I am not sure why.