How to prove this two condtions are equivalent Let $p$ be an odd prime and $a_1, a_2,...,a_p$ be integers. Prove that the following two conditions are equivalent:
$1)$ ：There exists a polynomial $P(x)$ with degree $\leq \frac{p-1}{2}$ such that $P(i) \equiv a_i \pmod p$ for all $1 \leq i \leq p$
$2)：$ foy any integer $k(0\le k\le \dfrac{p-3}{2})$,we have
$$\sum_{i=1}^{p}a_{i}i^k\equiv 0\pmod p$$
This problem is from when I deal 2015CMO3 problem at last step.seelinks
I think use this well konwn
$$\sum_{i=1}^{p}i^m\equiv 0\pmod p,0\le m<p-1,m\in Z$$
and
$$\sum_{i=1}^{p}i^m\equiv 1+1+\cdots+1=-1\pmod p,m=p-1,m\in Z$$
also see: Polynomial interpolating sequence mod p has small degree
But I can't it.Thanks
 A: Part 1. $(1)\implies (2)$.
Write
$$P(x)=\sum_{i=0}^{\frac{p-1}2}c_ix^i,$$
where $c_i$ may be $0$. Then, for any $0\leq k\leq \frac{p-3}2$,
$$\sum_{x=1}^pa_xx^k=\sum_{x=1}^px^kP(x)=\sum_{x=1}^px^k\sum_{i=0}^{\frac{p-1}2}c_ix^i=\sum_{i=0}^{\frac{p-1}2}c_i\sum_{x=1}^px^{k+i};$$
since each $k+i$ is at most $\frac{p-1}2+\frac{p-3}2=p-2$, the inner sums are all $0$, so this sum is $0$.
Part 2. $(2)\implies (1)$.
Consider the polynomial
$$P(x)=\sum_{y=1}^pa_y\big(1-(x-y)^{p-1}\big).$$
At any $x\in\{1,2,\dots,p\}$, all the terms with $y\neq x$ give $0$ modulo $p$ (using Fermat's little theorem), while the term with $y=x$ gives $a_x$, so $P(x)\equiv a_x\pmod p$. We need only show that $\deg P\leq \frac{p-1}2$. Indeed, write
\begin{align*}
P(x)
&=\sum_{y=1}^p a_y-\sum_{y=1}^p a_y(x-y)^{p-1}\\
&=-\sum_{y=1}^pa_y\sum_{j=0}^{p-1}\binom{p-1}jx^j(-y)^{p-1-j}\\
&=\sum_{j=0}^{p-1}x^j\binom{p-1}j(-1)^{p-j}\sum_{y=1}^pa_yy^{p-1-j}.
\end{align*}
For $j>\frac{p-1}2$, the inner sum is $\sum_{y=1}^p a_yy^k$ for $k\leq \frac{p-3}2$, and is thus $0$. So, the coefficient of $x^j$ in $P(x)$ for $j>\frac{p-1}2$ is $0$, and thus $\deg P\leq \frac{p-1}2$ as desired.
