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{array}{ll}0& p-1\nmid k\\ -1& p-1\mid k\end{array}(\mathrm{mod}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(\mathrm{mod}p)(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(\mathrm{mod}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(\mathrm{mod}p)(1\le i\le p-2)$$ $$a_0^{p-1}+a_1^{p-1}+\cdots +a_{p-1}^{p-1}\equiv -1(\mathrm{mod}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_1{x}^{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(\mathrm{mod}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(\mathrm{mod}p)$ Contradiction. So there exists a $0\le j\le p-1$ such that $a_j\equiv 0(\mathrm{mod}p)$ and therefore $b_p\equiv 0(\mathrm{mod}p)$. Now by Newton identities we have $$\{\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\\ ⋮\\ S_{p-1}+b_1{S}_{p-2}+\cdots +b_{p-2}{S}_1+(p-1)b_{p-1}=0\end{array}$$ Hence $$S_1+b_1=0,S_1\equiv 0(\mathrm{mod}p)\Rightarrow b_1\equiv 0(\mathrm{mod}p)$$ $$\begin{gathered} S_2+b_1{S}_1+2b_2=0,S_1\equiv S_2\equiv 0(\mathrm{mod}p)\Rightarrow 2b_2\equiv 0(\mathrm{mod}p)\Rightarrow b_2\equiv 0(\mathrm{mod}p) \\ ⋮ \end{gathered}$$ $$\begin{gathered} 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(\mathrm{mod}p) \\ \Rightarrow (p-2)b_{p-2}\equiv 0(\mathrm{mod}p)\Rightarrow b_{p-2}\equiv 0(\mathrm{mod}p) \end{gathered}$$

we have ${\sum }_{i=0}^{p-1}f(i{)}^s\equiv 0(\mathrm{mod}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(\mathrm{mod}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\{ $$\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(\mathrm{mod}p)\\ \Rightarrow (p-1)b_{p-1}\equiv 1(\mathrm{mod}p)\Rightarrow b_{p-1}\equiv -1(\mathrm{mod}p)\end{array}$$ \right.