# 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.

• It seems like $f(0) \equiv 1 \text{ mod p}$ (rather than $0 \text{ mod p}$) for any $n$?
– John
Feb 20 '15 at 17:05
• @John: $f(0)\equiv 1$ and $f(p-1)\equiv -(-1)^n$, so $n$ has to be even. Then, $f(p-1)\equiv p-1.$ Feb 20 '15 at 17:09
• Oh ... the condition is not that $f(m) \equiv m \text{ mod p}$, just that the sets are equivalent? (I saw the parallel between the lhs and rhs and may have added an incorrect constraint.)
– John
Feb 20 '15 at 17:12
• @John: The sets are equivalent. That's what I meant. Feb 20 '15 at 17:13
• There is a lot of literature on such polynomials, creatively called permutation polynomials.
– quid
Feb 20 '15 at 19:10

(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.

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$.

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.