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.

  • $\begingroup$ It seems like $f(0) \equiv 1 \text{ mod p}$ (rather than $0 \text{ mod p}$) for any $n$? $\endgroup$ – John Feb 20 '15 at 17:05
  • $\begingroup$ @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.$ $\endgroup$ – mathlove Feb 20 '15 at 17:09
  • $\begingroup$ 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.) $\endgroup$ – John Feb 20 '15 at 17:12
  • $\begingroup$ @John: The sets are equivalent. That's what I meant. $\endgroup$ – mathlove Feb 20 '15 at 17:13
  • 1
    $\begingroup$ There is a lot of literature on such polynomials, creatively called permutation polynomials. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.