Put $S(k)=\sum_{i=0}^n a_{i}x_{i}^k$ and $P(x)=x(x-1)...(x-r)$ It is well-known that $P(x) \equiv 0 (\mod (r+1)!)$ for all $x \in Z$(1) From the condition $S(1)=S(2)=...=S(r)=0$ so that $S(r+1)=\sum_{i=0}^n a_{i}P(x_{i})$ From (1) $\Longrightarrow S(r+1) \equiv 0 (\mod (r+1)!) \Longrightarrow S(r+1) \equiv 0 (mod (r+1))$ We investigate this problem with two cases: .If $m \in P$ then $\sum_{i=0}^n a_{i}x_{i}^m \equiv \sum_{i=0}^k a_{i}x_{i} \equiv 0 (\mod m)$ So that $\sum_{i=0}^n a_{i}x_{i}^m \equiv 0 (\mod m)$ .If $m$ isn't a prime number $\Longrightarrow (r+1)! \equiv 0 (\mod m) (\forall m \in \{r+1,r+2,...,2r+1\})$ Now,$S(m)=a_{0}P(x_{m-(r+1)})+a_{1}P(x_{m-r})+...+a_{r}P(x_{m-1}) \equiv 0 (\mod (r+1)!)$ $\Longrightarrow S(m) \equiv 0 (\mod m)$ For all $m \in \{r+1,r+2,...,2r+1\}$ and $m$ isn't a prime number From two cases,It follows that:$S(m) \equiv 0 (\mod m)$ for all $m \in \{r+1,r+2,...,2r+1\}$ So that the problem is proved. Remark:From this method we can also prove the problem (From Poland Mathematical Olympiad): Given $k \in N,k\geq 2$ and $a_{1},a_{2},...,a_{n} \in Z$satisfying: $a_{1}+2^{i}a_{2}+...+n^{i}a_{n}=0$ for all $1 \leq i \leq (k-1)$ Prove that:$a_{1}+2^{k}a_{2}+...+n^{k}a_{n} \equiv 0 (\mod k!)$

Very, very nice ! Can you just elaborate a little more on that equality $S(m)=a_{0}P(x_{m-(r+1)})+a_{1}P(x_{m-r})+...+a_{r}P(x_{m-1}) (\mbox{ mod } (r+1)!)$

{x} wrote: Very, very nice ! Can you just elaborate a little more on that equality $S(m)=a_{0}P(x_{m-(r+1)})+a_{1}P(x_{m-r})+...+a_{r}P(x_{m-1}) (\mbox{ mod } (r+1)!)$ Actually I don't understand how to arrive at this equality, namely because I don't know what $a_r$ is supposed to be if $r>n$ and so on... But I have to admit that I didn't really give thought to the identity.. shobber wrote: Let $a_1$, $a_2$, $\dots$, $a_n$ and $x_1$, $x_2$, $\dots$, $x_n$ be integers and $r \ge 2$ be an integer. It is known that $\sum_{j=1}^{n} a_j x_j^k =0$ for $k=1$, $2$, $\dots$, $r$. Prove that \[ \sum_{j=1}^{n} a_j x_j^m \equiv 0 \mod m\] holds for all $m \in \{ r+1$, $r+2$, $\dots$, $2r+1 \}$. Proof. Fix $m=\prod p_i^{\alpha_i}$ and rewrite $\sum a_j x_j^m$ as \[\sum_{j=1}^{n} a_j x_j^m=\sum_{j=2}^{n} a_jx_j^m-x_1^{m-k}\left(\sum_{j=2}^{n} a_jx_j^k\right)=\sum_{j=2}^{n}a_jx_j^k\left(x_j^{m-k}-x_1^{m-k}\right).\] It's clearly enough to prove that this sum is congruent to zero modulo $p_i^{\alpha_i}$ for every $i$. Fix $i$ and suppose wlog that $p_i \not | x_1$ (if all the $x_j$'s are congruent to zero modulo $p_i$, just divide all of them by $p_i^{\alpha}$ for an appropriate $\alpha$). Moreover, let $k=m-t\varphi(m)>0$, $t$ as large as possible. We evidently have $p_i^{\alpha_i-1}| k$ and therefore $k \ge p_i^{\alpha_i-1} \ge a_i$. We now prove that $a_jx_j^k\left( x_j^{m-k}-x_1^{m-k}\right) \equiv 0 \mod p_i^{\alpha_i}$ holds true for every $j$. If $p_i\not | x_j$, then we have $x_j^{m-k} = x_j^{t\varphi(m)} \equiv 1 \equiv x_1^{t\varphi(m)} \mod p_i^{\alpha_i}$. If $p_i |x_j$, then $p_i^{\alpha_i} | x_j^{\alpha_i} | x_j^k$, since we have shown that $k \ge a_i$. This completes the proof.

let $m=k\phi (m)+q$, where $k,q$ are integers with $k\ge 1$ and $0\le q\le \phi (m) $, $ \phi $ is Euler totient function. Then we have $q\le min\{ \phi(m),m-\phi(m) \} \le \lfloor \frac{m}{2} \rfloor $.