= Solution
Reduce the <polynomial> modulo $p$, obtaining a nonzero degree-$d$ <polynomial> over the field $\mathbb F_p$. If $a$ is a root, <polynomial> division gives $\bar f(X)=(X-a)h(X)$. Any different root $b$ is a root of $h$, because $b-a\ne0$ is invertible. Induction on degree therefore proves \b[there are at most $d$ distinct roots modulo $p$].
Every nonzero residue is a root of $X^{p-1}-1$ by <Fermat's little theorem>. The difference between this monic <polynomial> and the product over all its $p-1$ nonzero roots has degree at most $p-2$, yet has $p-1$ roots. The root bound forces it to vanish identically over $\mathbb F_p$. Thus all coefficients of the corresponding integer <polynomial> are divisible by $p$.
For the requested failure modulo $p^2$, take $p=7$: $6!+1=721=7\cdot103$, and $103$ is not divisible by seven. Hence \b[the prime-square strengthening fails], even though some special primes do satisfy it.
Back to article page
