## Polynomial residues

If p is a prime then $m^p \equiv m$ (mod p) for all integers m. So the polynomial $f = X^p-X \in \mathbb{Z}[X]$ has the property that $f(m) \equiv 0$ (mod p) for all integers m. Since $\mathbb{Z}_p$ is an integral domain, any polynomial in $\mathbb{Z}[X]$ of degree d that is not divisible by p has at most d roots in $\mathbb{Z}_p$. The degree of a polynomial that vanishes identically on $\mathbb{Z}_p$ must therefore be at least p, so $X^p-X$ is also minimal in that sense. What can we say if we replace the prime p by just any positive integer n? In other words, what can we say about $f \in \mathbb{Z}[X]$ if $f(m) \equiv 0$ (mod n) for all integers m? This question was studied by Aubrey Kempner in the 1920’s. Here are some of his results:

“Suppose $f \in \mathbb{Z}[X]$ has degree d and vanishes identically on $\mathbb{Z}_n$. Let $\dfrac{n}{d!} = \dfrac{m}{q}$ for coprime integers m and q. Then f is divisible by m.”

In particular if the coefficients of f have no common factor then n must divide d!, the factorial of its degree. For prime n this implies that f is divisible by n unless d is at least n and this is in accordance with the first paragraph above. To see that this bound is sharp for any n define the binomial polynomials $\binom{x}{d}$ by

$\displaystyle \binom{x}{d} = \dfrac{x (x-1) \dotsc (x-d+1)}{d!}$.

The binomial polynomials take integer values at integer arguments (the number of ways to choose d elements from a set of x). Therefore, if n divides d! then $d! \binom{x}{d}$ is a monic polynomial of degree d in $\mathbb{Z}[X]$ that vanishes identically on $\mathbb{Z}_n$. The other way around, suppose $f \in \mathbb{Z}[X]$ has degree d and $f(m) \equiv 0$ (mod n) for all integers m. Let $\dfrac{m}{q} = \dfrac{n}{d!}$ as before. Then there exist coefficients $c_0, \dotsc, c_d \in \mathbb{Z}$ such that

$f(x) = n \displaystyle \sum_{k=0}^d c_k \binom{x}{k} = \frac{m}{q} \sum_{k=0}^d c_k d! \binom{x}{k}$.

For each k the polynomial $c_k d! \binom{x}{k}$ has integer coefficients and since m and q are coprime the equation above implies that m divides f.