Putnam 2011, Problem B-6

Let $p$ be an odd prime. Show that for at least $(p+1)/2$ values of $n$ in $\{0, 1, 2, \ldots, p-1\}$,
$$\sum_{k=0}^{p-1} k! n^k$$
is not divisible by $p$.


Solution:
In order to interpret the problem statement, one must choose a convention for the value of \(0^0\); we will take it to equal \(1\). (If one takes \(0^0\) to be \(0\), then the problem fails for \(p = 3\).)  
**First solution.** By Wilson’s theorem,  
\[
k!(p - 1 - k)! \equiv (-1)^k (p - 1)! \equiv (-1)^{k+1} \pmod{p},
\]  
so we have a congruence of Laurent polynomials  
\[
\sum_{k=0}^{p-1} k! x^k \equiv \sum_{k=0}^{p-1} \frac{(-1)^{k+1} x^k}{(p - 1 - k)!} \pmod{p}
\]  
\[
\equiv -x^{p-1} \sum_{k=0}^{p-1} \frac{(-x)^{-k}}{k!} \pmod{p}.
\]  
Replacing \(x\) with \(-1/x\), we reduce the original problem to showing that the polynomial  
\[
g(x) = \sum_{k=0}^{p-1} \frac{x^k}{k!}
\]  
over \(\mathbb{F}_p\) has at most \((p - 1)/2\) nonzero roots in \(\mathbb{F}_p\). To see this, write  
\[
h(x) = x^p - x + g(x)
\]  
and note that by Wilson’s theorem again,  
\[
h'(x) = 1 + \sum_{k=1}^{p-1} \frac{x^{k-1}}{(k - 1)!} = x^{p-1} - 1 + g(x).
\]  
If \(z \in \mathbb{F}_p\) is such that \(g(z) = 0\), then \(z \neq 0\) because \(g(0) = 1\). Therefore, \(z^{p-1} = 1\), so \(h(z) = 0\) and so \(z\) is at least a double root of \(h\). Since \(h\) is a polynomial of degree \(p\), there can be at most \((p - 1)/2\) zeroes of \(g\) in \(\mathbb{F}_p\), as desired.  
**Second solution.** (By Noam Elkies) Define the polynomial \(f\) over \(\mathbb{F}_p\) by  
\[
f(x) = \sum_{k=0}^{p-1} k! x^k.
\]  
Put \(t = (p - 1)/2\); the problem statement is that \(f\) has at most \(t\) roots modulo \(p\). Suppose the contrary; since \(f(0) = 1\), this means that \(f(x)\) is nonzero for at most \(t - 1\) values of \(x \in \mathbb{F}_p^*\). Denote these values by \(x_1, \dots, x_m\), where by assumption \(m < t\), and define the polynomial \(Q\) over \(\mathbb{F}_p\) by  
\[
Q(x) = \prod_{k=1}^m (x - x_m) = \sum_{k=0}^{t-1} Q_k x^k.
\]  
Then we can write  
\[
f(x) = \frac{P(x)}{Q(x)} (1 - x^{p-1})
\]  
where \(P(x)\) is some polynomial of degree at most \(m\). This means that the power series expansions of \(f(x)\) and \(P(x)/Q(x)\) coincide modulo \(x^{p-1}\), so the coefficients of \(x^t, \dots, x^{2t-1}\) in \(f(x)Q(x)\) vanish. In other words, the product of the square matrix  
\[
A = ((i + j + 1)!)_{i,j=0}^{t-1}
\]  
with the nonzero column vector \((Q_{t-1}, \dots, Q_0)\) is zero. However, by the following lemma, \(\det(A)\) is nonzero modulo \(p\), a contradiction.  
**Lemma 1.** For any nonnegative integer \(m\) and any integer \(n\),  
\[
\det((i + j + n)!)_{i,j=0}^m = \prod_{k=0}^m k!(k + n)!.
\]  
*Proof.* Define the \((m + 1) \times (m + 1)\) matrix \(A_{m,n}\) by \((A_{m,n})_{i,j} = \binom{i + j + n}{i}\); the desired result is then that \(\det(A_{m,n}) = 1\). Note that  
\[
(A_{m,n-1})_{ij} = \begin{cases} 
(A_{m,n})_{ij} & i = 0 \\
(A_{m,n})_{ij} - (A_{m,n})_{(i-1)j} & i > 0;
\end{cases}
\]  
that is, \(A_{m,n-1}\) can be obtained from \(A_{m,n}\) by elementary row operations. Therefore, \(\det(A_{m,n}) = \det(A_{m,n-1})\), so \(\det(A_{m,n})\) depends only on \(m\). The claim now follows by observing that \(A_{0,0}\) is the \(1 \times 1\) matrix with entry \(1\) and that \(A_{m,-1}\) has the block representation \(\begin{pmatrix} 1 & * \\ 0 & A_{m-1,0} \end{pmatrix}\). \(\square\)