Polynomial and Permutation

Question

Let $p$ a prime odd number, $P\in (\mathbb Z/p\mathbb Z)[x]$ with $\deg(P)<p$ and $P(x)=a_0+\dots+a_{p−1}x^{p−1}$. Is it true if $a_{p−1}\neq 0$ then the polynomial function associed to $P$ is not a permutation of $\mathbb Z/p\mathbb Z$ ?

Answer 1

Suppose that polynomial $P(x)=a_0+a_1x+\ldots+a_{p-1}x^{p-1}$ with $a_{p-1}\neq 0$ satisfies the condition $$ P(\mathbb{Z}/p\mathbb{Z})=\mathbb{Z}/p\mathbb{Z}. $$ Then, it's clear that $$ \sum_{k=0}^{p-1}P(k)\equiv \sum_{k=0}^{p-1}k=\frac{p(p-1)}{2}\equiv 0\pmod p. $$ However, it's well-known that for $m\ge 1$ $$ 0^m+1^m+\ldots+(p-1)^m\equiv \begin{cases} 0,& p-1\nmid m, \\ -1,& p-1\mid m. \end{cases} $$ Hence, $$ \sum_{k=0}^{p-1}P(k)\equiv a_0\cdot p+a_1\cdot 0+\ldots+a_{p-2}\cdot 0+a_{p-1}\cdot (-1)\equiv -a_{p-1}. $$ Thus, $a_{p-1}\equiv 0\pmod p$, as desired.

Answer 2

For an odd prime $p$, let $$ P=a_0+\cdots+a_{p-1}x^{p-1}\in (\mathbb Z/p\mathbb Z)[x] $$ and suppose that $P$, when regarded as a function from $\mathbb Z/p\mathbb Z$ to $\mathbb Z/p\mathbb Z$, is a permutation of $\mathbb Z/p\mathbb Z$.

Claim:$\;a_{p-1}=0$.

Proof:

For $k\in\{0,...,p-1\}$, let $X_k=\{0,...,p-1\}{\large{\setminus}}\{k\}$.

By Lagrange interpolation $$ P(x)=\sum_{k=0}^{p-1}P(k)\bigl(f_k(x)\bigr) $$ where $$ f_k(x)= \prod_{\large{j\in X_k}} \frac {x-j} {k-j} $$ For each $k\in\{0,...,p-1\}$, we have $$ \prod_{\large{j\in X_k}} (k-j) \; = \; \prod_{i=1}^{p-1}i \; = \; (p-1)! $$ so by Wilson's theorem, the leading coefficient $b_k$ of $f_k$ is $-1$.

Then we get \begin{align*} a_{p-1}&=\, \sum_{k=0}^{p-1} P(k)(-1) &&\bigl(\text{since $\deg{f_k}=p-1$ and $b_k=-1$}\bigr) \\[4pt] &=\, -\sum_{k=0}^{p-1} P(k) \\[4pt] &=\, -\sum_{k=0}^{p-1} k &&\bigl(\text{since $P$ is a permutation of $\mathbb Z/p\mathbb Z$}\bigr) \\[4pt] &=\, -\frac{p(p-1)}{2} \\[4pt] &=\, 0 \\[4pt] \end{align*} as was to be shown.