Iranian Mathematical Olympiad

Lemma. Let $p$ be an odd prime number and $k$ a positive integer then we have
$$\sum_{i=0}^{p-1} i^k \equiv \begin{cases} 0 & p-1 \nmid k \\ -1 & p-1 \mid k \end{cases} \pmod{p}.$$
Proof. If $p-1 \nmid k$ the statement is obvious by Fermat Little Theorem. For $p-1 \nmid k$
consider $g$ a primitive root modulo $p$ then
$$\sum_{i=0}^{p-1} i^k \equiv \sum_{i=1}^{p-1} i^k \equiv \sum_{i=1}^{p-1} g^{ik} \equiv \frac{g^{k(p-1)} - 1}{g^k - 1} \equiv 0 \pmod{p} \quad (p-1 \nmid k \Rightarrow g^k \not\equiv 1).$$
Now for every polynomial $f \in \mathbb{Z}[x]$ with $f(x) = \sum_{n=0}^{m} a_n x^n$, we have
$$\sum_{i=0}^{p-1} f(i) \equiv \sum_{i=0}^{p-1} \sum_{n=0}^{m} a_n i^n \equiv \sum_{n=0}^{m} a_n \sum_{i=0}^{p-1} i^n \equiv - \sum_{p-1 \mid n, n>0} a_n \pmod{p}.$$
Therefore if $f(0), f(1), \dots, f(p-1)$ are a complete system of residues modulo $p$ then

$$a_0^i + a_1^i + \cdots + a_{p-1}^i \equiv 0 \pmod{p} \quad (1 \le i \le p-2)$$
$$a_0^{p-1} + a_1^{p-1} + \cdots + a_{p-1}^{p-1} \equiv -1 \pmod{p}$$
Then $\{a_0, a_1, \dots, a_{p-1}\}$ is a complete system of residues. Now Suppose that
$$g(x) = (x - a_0)(x - a_1)\cdots(x - a_{p-1}) = x^p + b_1x^{p-1} + \cdots + b_{p-1}x + b_p$$
and $S_i = a_0^i + a_1^i + \cdots + a_{p-1}^i$ for $i \in \mathbb{N}$.
If for all $0 \le i \le p-1$ we have $a_i \not\equiv 0 \pmod{p}$ then invoking the Fermat little theorem we have $1 \equiv a_0^{p-1} + a_1^{p-1} + \cdots + a_{p-1}^{p-1} \equiv \frac{1+1+\cdots+1}{p \text{ times}} \equiv 0 \pmod{p}$
Contradiction. So there exists a $0 \le j \le p-1$ such that $a_j \equiv 0 \pmod{p}$ and therefore $b_p \equiv 0 \pmod{p}$. Now by Newton identities we have
$$\left\{ \begin{array}{l} S_1 + b_1 = 0 \\ S_2 + b_1 S_1 + 2b_2 = 0 \\ S_3 + b_1 S_2 + b_2 S_1 + 3b_3 = 0 \\ \vdots \\ S_{p-1} + b_1 S_{p-2} + \cdots + b_{p-2} S_1 + (p-1)b_{p-1} = 0 \end{array} \right.$$
Hence
$$S_1 + b_1 = 0, S_1 \equiv 0 \pmod{p} \Rightarrow b_1 \equiv 0 \pmod{p}$$
$$S_2 + b_1 S_1 + 2b_2 = 0, S_1 \equiv S_2 \equiv 0 \pmod{p} \Rightarrow 2b_2 \equiv 0 \pmod{p} \Rightarrow b_2 \equiv 0 \pmod{p} \\ \vdots$$
$$S_{p-2} + b_1 S_{p-3} + \cdots + b_{p-3} S_1 + (p-2)b_{p-2} = 0, S_1 \equiv S_2 \equiv \cdots \equiv S_{p-2} \equiv 0 \pmod{p} \\ \Rightarrow (p-2)b_{p-2} \equiv 0 \pmod{p} \Rightarrow b_{p-2} \equiv 0 \pmod{p}$$

we have $\sum_{i=0}^{p-1} f(i)^s \equiv 0 \pmod{p}$ for $1 \le s \le p-2$ so $f(x), (f(x))^2, \dots, (f(x))^{p-2}$ are all
0-residue and $-\sum_{i=0}^{p-1} f(i)^{p-1} \equiv 1 \pmod{p}$ so $(f(x))^{p-1}$ is 1-residue.
Now for reverse by (1) it suffices to prove that if for $p$ numbers $a_0, a_1, \dots, a_{p-1} \in \mathbb{Z}$
we have

and
$$$$
$\left\{ \right.$ $$\begin{array}{l} S_{p-1} + b_1 S_{p-2} + \cdots + b_{p-2} S_1 + (p-1)b_{p-1} = 0 \\ S_1 \equiv S_2 \equiv \cdots \equiv S_{p-2} \equiv 0, S_{p-1} \equiv -1 \pmod{p} \\ \Rightarrow (p-1)b_{p-1} \equiv 1 \pmod{p} \Rightarrow b_{p-1} \equiv -1 \pmod{p} \end{array}$$ $\left. \right.$