This was a nice problem. Here is a sketch of the solution: All mods are taken mod $p$. Let $(p-1 , k) = d$. First notice that $deg(P) \le p-1$. Then by bezout we have $P(a_{i+d}) \equiv P(a_i)$ and so $P(x) \equiv (x-a_i)(x-a_{i+d})\cdots (x-a_{i+p-1-d})Q_i(x) + P(a_i)$ and so $deg(P) \ge \frac{p-1}{d}$ Now notice that if $g$ is a primitive root, by letting $a_i = g^i$ we can see that $x^{\frac{p-1}{d}}$ works (if $d = 1$ we have $P(x) \equiv (x^{p-1} -1)Q(x)+P(1)$ but $deg(P) \le p-1$ and so $Q$ must be constant and so $P(x) \equiv cx^{p-1} -c+P(1)$ and so $P(x) = ax^{p-1}+b$) and so $deg(P) \le \frac{p-1}{d}$ So we have $deg(P) = \frac{p-1}{d}$ and so $\forall i: Q_i$ must be constant. Now finish with Newton's identities.