When are polynomial functions over finite fields linear?

Question

If I have a polynomial function $f:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ such that $f(x) = x^n$, under what circumstances will $f$ be linear? I think $f$ can only be linear if $n = p$, as then the 'freshman's dream' will be true, i.e. $(x + y)^p = x^p + y^p$. Is my hunch correct? How would I formalize this into a full proof?

Answer 1

I assume $p > 2$.

If $f(x) = x^n$ to be linear, then $x^n + y^n = (x + y)^n$ should hold for all $x, y \in \Bbb Z/p\Bbb Z$.

Since we have $1^n = 1$, by induction on $k$ we will get $k^n = k$ (as elements of $\Bbb Z/p\Bbb Z$) for all $k$.

In particular, $k^{n - 1} = 1$ holds for a primitive root $k$ mod $p$, which implies that $p - 1 \mid n - 1$.

Therefore $n$ is of the form $1 + (p - 1)t$ with $t \in \Bbb Z$.

On the other hand, it is easy to see that all such $n$ satisfy $x^n + y^n = (x + y)^n$ for all $x, y$.

---

For general polynomials (i.e. not necessarily of the form $x^n$), we notice that any function from $\Bbb Z/p\Bbb Z$ to $\Bbb Z/p\Bbb Z$ can be expressed as a polynomial. Two polynomials represent the same function if and only if their difference is a multiple of $x^p - x$.

Therefore, it suffices to determine all linear functions from $\Bbb Z/p\Bbb Z$ to itself. These of course are simply functions of the form $x \mapsto \lambda x$ for a fixed $\lambda \in \Bbb Z/p\Bbb Z$.