62nd Ukrainian National Mathematical Olympiad, Third Round, Second Tour

Example: $Q(x)=x^{p-2}-1$. For any $i<j<p$: $$Q(j)-Q(i)=y^{p-2}-x^{p-2}\equiv \frac{1}{y}-\frac{1}{x}(\mathrm{mod}p),$$ which clearly isn't divisible by $p$, and $$jQ(j)-iQ(i)=(y^{p-1}-x^{p-1})-(y-x)\equiv (x-y)(\mathrm{mod}p)$$ also isn't divisible by $p$.

Suppose that there exists such a polynomial of smaller degree. It follows from the statement that all of $Q(1),Q(2),\dots ,Q(p-1)$ give different remainders modulo $p$, and also $1Q(1),2Q(2),\dots ,(p-1)Q(p-1)$ give different remainders modulo $p$. Let's use the following fact: $1^k+2^k+\cdots +(p-1{)}^k\equiv 0(\mathrm{mod}p)$ for any $k$ from $1$ to $p-2$. Then consider $1Q(1)+2Q(2)+\cdots +(p-1)Q(p-1)$. From the fact above, this number is $0$ modulo $p$ (as each degree in the polynomial $xQ(x)$ is in the range $[1,p-2]$). Suppose that among the numbers $1P(1),\dots ,(p-1)P(p-1)$ there are all remainders modulo $p$, except for $x$. Then: $$0\equiv 0+1+\cdots +(p-1)\equiv 1Q(1)+2Q(2)+\cdots +(p-1)Q(p-1)+x\equiv x(\mathrm{mod}p),$$ so $1Q(1),2Q(2),\dots ,(p-1)Q(p-1)$ modulo $p$ give remainders $1,2,\dots ,p-1$ in some order. Then none of $Q(1),Q(2),\dots ,Q(p-1)$ is divisible by $p$, and they also give remainders $1,2,\dots ,p-1$ in some order. But then: $$(p-1)!\equiv 1Q(1)\times 2Q(2)\times \cdots \times (p-1)Q(p-1)\equiv (p-1){!}^2(\mathrm{mod}p),$$ which, by the Wilson theorem, gives, $-1\equiv 1(\mathrm{mod}p)$, this contradiction completes the proof.