Number theory, prime numbers

Question

prove that for all prime numbers $p>2000$ the sum $$1+2^{2000}+3^{2000}+...+(p-1)^{2000}$$ is divisible by $p$

I tried this with primes smaller then $2000$, but I can't find a general rule.

Answer 1

Pick any non-zero $a$ such that $a^{2000} \not \equiv 1 \pmod p$ (if no such $a$ exist then every number in the sum is congruent to one and hence the sum is divisible by $p$). Now if we multiply all the numbers $1 \ldots p-1$ by $a$ we'll get some permutation of $1 \ldots p-1$. So $(1^{2000} + \cdots + (p-1)^{2000}) \cdot a^{2000} = (1^{2000} + \cdots + (p-1)^{2000})$. Since $a^{2000} \not \equiv 1 \pmod p$ we must have $1^{2000} + \cdots + (p-1)^{2000} \equiv 0 \pmod p$.

Alternatively, you can pick any primitive root $g$ modulo $p$ and then the sum is equal to $g^{0} + g^{1 \cdot 2000} + g^{2\cdot 2000} + ... + g^{(p-2) \cdot 2000} = \frac{g^{2000(p-1)} - 1}{g^{2000}-1}$ which is also divisible by $p$.

Answer 2

You don't need $p>2000$. As suggested by alkabary, let us argue by induction.

Let us show that $S_{A}=\sum_{x\in{\frac{\mathbb Z}{p\mathbb Z}}} A(x)=0$ for any integer polynomial $A$, by induction on the degree $d$ of $A$.

If $d=0$, then $A$ is a constant $a\in{\mathbb Z}$, so that $S_A=pa=0$.

Suppose now that $d>0$, and that the results holds for all polynomials of degree $<d$. Let us denote the leading coefficent of $A$ by $a$. Then $B(X)=A(X)-aX^d$ has degree $<d$. The polynomial $C(X)=X^d-\frac{X^{d+1}-(X-1)^{d+1}}{d+1}$ has degree $<d$ also, and

$$ S_A=\sum_{k=1}^{p} A(k)=\sum_{k=1}^{p} ak^d+B(k)= \sum_{k=1}^{p} a\bigg(\frac{k^{d+1}-(k-1)^{d+1}}{d+1}+C(k)\bigg)+B(k)= a(p^{d+1}-0^{d+1})+\sum_{k=1}^{p} aC(k)+B(k)=0 $$

by the induction hypothesis applied to $aC+B$ (whose degree is $<d$). This concludes the proof.