Throughout the proof we will compute modulo $p$, every congruence is modulo $p$. Let $Q(x)$ be the polynomial. Assume that $k | p-1$, $ k > 1$ and $Q$ attains every possible value modulo $p$. Since $Q(x) \equiv Q(x + p)$, the polynomial attains different values at $x = 0, 1, 2, \dots , p-1.$ Now suppose indirectly that the leading coefficient of $Q$ is not divisible by $p$. Let $c = \frac{p-1}{k}$ and let $R(x)=Q^c(x)c=b_(p-1)x^(p-1)+\dots +b_0$. Firstly we can see that in $R$ the coefficient $b_{p-1}$ is not $0$ modulo $p$ since the leading coefficient of $Q$ is nonzero and $b_{p-1}=(a_k)^c$. Let us consider the following sum: $R(1)+\dots+R(j)+\dots+R(p-1)$ Since $k > 1$ and $k$ is a divisor of $p-1$, $c$ is a positive integer smaller than $p-1$. By our hypothesis $Q(x)$ attains every value modulo $p$, in other words $Q(0), Q(1),\dots ,Q(p - 1) $is a permutation of$ 0, 1,\dots ,p -1$, so the sum can we written the following way: $Q(1)^c+ . . . +Q(p-1)^c \equiv 1^c+2^c+ . . . +(p-1)^c \equiv 0$ on the other hand: $R(1)+...+R(j)+...+R(p-1) \equiv -b_{p-1}$ since $1^k+. . .(p-1)^ k \equiv 0$ if $k=0,1,...,p-2$ So $0 \equiv -b_{p-1}$, which is a contradiction since we have shown already that $b_{p-1}$ is nonzero. So the leading coefficient of $Q$ must be divisible by $p$.

What am I missing? An equivalent restatement of this problem would be to show that the only polynomials in $\mathbb{F} _p [x]$ that have a degree less than $p$ and is surjective on $\mathbb{F} _p$ are $x+c$ for $c \in \mathbb{F}_p$. Am I wrong? But without breaking out abstract algebra, there's a nice lemma with primitive roots that can be used for an alternative solution to this problem: $$ \sum _{j = 0} ^{p-1} j^t = \begin{cases} -1 \ \text{if} \ t = p-1 \\ 0 \ \text{if} \ t = 0, 1, \dots , p-2 \end{cases}$$ (should have reread the @above's post, they use it already, o well)

OmicronGamma wrote: What am I missing? An equivalent restatement of this problem would be to show that the only polynomials in $\mathbb{F} _p [x]$ that have a degree less than $p$ and is surjective on $\mathbb{F} _p$ are $x+c$ for $c \in \mathbb{F}_p$. Am I wrong? Actually this isn't even true. The set of functions $\mathbb{F}_p \rightarrow \mathbb{F}_p$ is isomorphic to $\mathbb{F}_p [x]/(x^p - x)$, meaning every function can be realized by a polynomial of degree less than $p$. Since linear polynomials are bijective in $\mathbb{F}_p$, we have $p(p-1)$ bijective polynomials by my misunderstanding above. But then there are $p!$ functions from $\mathbb{F}_p \rightarrow \mathbb{F}_p$. The discrepancy (for $p > 2$) suggests that there must be some bijective polynomial with degree greater than $1$ but less than $p$... Yikes.