Number theory, prime numbers 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. 
 A: 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$.
A: 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.
