Finding $n$ satisfying $\{1^n-0^n,2^n-1^n,\cdots,p^n-(p-1)^n\}\equiv \{0,1,\cdots,p-1\}\pmod p$ Background : About a month ago, a friend of mine taught me his findings about a few  polynomials which cover all the residue classes in mod $p$ where $p$ is a prime. Then, I began to consider the same problem for the other polynomials. Among some polynomials, $f(x)=(x+1)^n-x^n$ is the one that I can't grasp. So, here is my question. 

Question : For a given odd prime $p$, how can we find every positive integer $n$ satisfying the following condition?
Condition : For $f(x)=(x+1)^n-x^n$, 
  $$\{f(0),f(1),f(2),\cdots,f(p-1)\}\equiv \{0,1,2,\cdots,p-1\}\pmod p.$$
Remark : We want that $f(x)$ covers all the residue classes $\pmod p$. The condition is not $f(x)\equiv x\pmod p$.

I conjecture that the answer is $n=(p-1)m+2\ \ (m=0,1,2,\cdots)$, but I'm facing difficulty in proving that. Maybe I'm missing something important... Can anyone help?
The followings are what I've got.


*

*$f(0)\equiv 1.$

*$f(p-1)\equiv -(-1)^n\Rightarrow \text{$n$ has to be even}\Rightarrow f(p-1)\equiv p-1$.

*For $n=(p-1)m+r$, $f(x)\equiv (x+1)^r-x^r$ because $a^{p-1}\equiv 1$ for $a$ which is coprime to $p$. 

*$f\left(\frac{p-1}{2}\right)\equiv 0$.

*$f\left(\frac{p-1}{2}+a\right)+f\left(\frac{p-1}{2}-a\right)\equiv 0$ for any $a$. 
Added : I crossposted to MO.
 A: (This should really be a comment but its too long.)
I'm wondering if the information posted on the Wikipedia article on permutation polynomials is correct. It lists that if $g(x)$ is a permutation polynomial, then so is $ag(x+b)+c$ and $ax^3+bx$ is a permutation polynomial iff $-b/a$ is a quadratic non residue. Using this, I can prove that $r = 4$ is valid for all primes $ \equiv 3 \pmod 4$. However, this only seems to work for the prime $3$...
The depressed for $(x+1)^4-x^4$ using the transformation $x \rightarrow x - \frac{1}2$ and dropping the constant is $4x^3+x$. Multiplying across by $4^{-1}$ transforms this into $x^3+(4)^{-1}x$. Now if 
$$ \left( \frac{-4^{-1}}p \right) = (-1)^{\frac{p-1}2}(2^{-1})^{p-1} \equiv -1 \pmod p $$
so $r = 4$ should work but checking the prime $7$, we can see that the polynomial does not work.
A: To me problem seems more deeper and complicated than it looks. $n = (p-1)m + 2$ is one of the possible solutions if $m$ as such that $p \nmid n$.
If we want that $f(x)$ covers all residuals of $p$ we have to make sure that there are no two residual classes maps to the same class.
Say $k < p$ and $q < p$ maps to the same class. Then $f(k) - f(q) \equiv 0 (mod(p))$ Plugging it into function we get:
$$f(k)-f(q) \equiv (k-q)(P_{n-2}(k,q)) mod(p)$$ where $P_{n-2}$ is symmetrical polynomial of degree $n-2$. 
For example, for $n = 2: P_0 = 2$; for $n = 3: P_1 = 3(k+q+1)$; 
for $n = 4: P_2 = 4(k^2 + kq + q^2) + 6(k+q) + 4$ and so on. 
Polynomials are symmetric but higher degrees residual equation require different math theory be involved. 
Is it clear to see that we can find k,q so that $P_1 \equiv 0 (mod(p))$ It is not so easy to show for higher degrees when solution may not exists and be dependent on $p$. 
A: I'm posting an answer just to inform that the question has received an answer by Peter Mueller on MO.
The answer mentions that the expected answer is correct, and it is a theorem by Norman Johnson, see here. 
