Putnam 2008, Problem B-4

Let $p$ be a prime number. Let $h(x)$ be a polynomial with integer coefficients such that $h(0), h(1), \ldots, h(p^2 - 1)$ are distinct modulo $p^2$. Show that $h(0), h(1), \ldots, h(p^3 - 1)$ are distinct modulo $p^3$.

Solution:
We use the identity given by Taylor's theorem:
$$h(x+y) = \sum_{i=0}^{\deg(h)} \frac{h^{(i)}(x)}{i!} y^i.$$

In this expression, $h^{(i)}(x)/i!$ is a polynomial in $x$ with integer coefficients, so its value at an integer $x$ is an integer.

For $x = 0, \ldots, p-1$, we deduce that
$$h(x+p) \equiv h(x) + ph'(x) \pmod{p^2}.$$

(This can also be deduced more directly using the binomial theorem.) Since we assumed $h(x)$ and $h(x+p)$ are distinct modulo $p^2$, we conclude that $h'(x) \not\equiv 0 \pmod{p}$. Since $h'$ is a polynomial with integer coefficients, we have $h'(x) \equiv h'(x+mp) \pmod{p}$ for any integer $m$, and so $h'(x) \not\equiv 0 \pmod{p}$ for all integers $x$.

Now for $x = 0, \ldots, p^2 - 1$ and $y = 0, \ldots, p-1$, we write
$$h(x+yp^2) \equiv h(x) + p^2 y h'(x) \pmod{p^3}.$$

Thus $h(x), h(x+p^2), \ldots, h(x+(p-1)p^2)$ run over all of the residue classes modulo $p^3$ congruent to $h(x)$ modulo $p^2$. Since the $h(x)$ themselves cover all the residue classes modulo $p^2$, this proves that $h(0), \ldots, h(p^3 - 1)$ are distinct modulo $p^3$.

**Remark:** More generally, the same proof shows that for any integers $d,e > 1$, $h$ permutes the residue classes modulo $p^d$ if and only if it permutes the residue classes modulo $p^e$. The argument used in the proof is related to a general result in number theory known as Hensel's lemma.