Putnam 2019, Problem A-5

Let \(p\) be an odd prime number, and let \(\mathbb{F}_p\) denote the field of integers modulo \(p\). Let \(\mathbb{F}_p[x]\) be the ring of polynomials over \(\mathbb{F}_p\), and let \(q(x) \in \mathbb{F}_p[x]\) be given by
\[q(x) = \sum_{k=1}^{p-1} a_k x^k,\]
where
\[a_k = k^{(p-1)/2} \mod p.\]
Find the greatest nonnegative integer \(n\) such that \((x - 1)^n\) divides \(q(x)\) in \(\mathbb{F}_p[x]\).

Solution:
The answer is $\frac{p-1}{2}$. Define the operator $D = x\frac{d}{dx}$, where $\frac{d}{dx}$ indicates formal differentiation of polynomials. For $n$ as in the problem statement, we have $q(x) = (x-1)^n r(x)$ for some polynomial $r(x)$ in $\mathbb{F}_p$ not divisible by $x-1$. For $m = 0, \ldots, n$, by the product rule we have
$$(D^m q)(x) \equiv n^m x^m (x-1)^{n-m} r(x) \pmod{(x-1)^{n-m+1}}.$$

Since $r(1) \neq 0$ and $n \not\equiv 0$ (mod $p$) (because $n \leq \deg(q) = p-1$), we may identify $n$ as the smallest nonnegative integer for which $(D^n q)(1) \neq 0$.

Now note that $q = D^{(p-1)/2} s$ for
$$s(x) = 1 + x + \cdots + x^{p-1} = \frac{x^p - 1}{x - 1} = (x-1)^{p-1}$$
since $(x-1)^p = x^p - 1$ in $\mathbb{F}_p[x]$. By the same logic as above, $(D^n s)(1) = 0$ for $n = 0, \ldots, p-2$ but not for $n = p-1$. This implies the claimed result.

**Remark.** One may also finish by checking directly that for any positive integer $m$,
$$\sum_{k=1}^{p-1} k^m \equiv \begin{cases} -1 \pmod{p} & \text{if } (p-1)|m \\ 0 \pmod{p} & \text{otherwise.} \end{cases}$$

If $(p-1)|m$, then $k^m \equiv 1$ (mod $p$) by the little Fermat theorem, and so the sum is congruent to $p-1 \equiv -1$ (mod $p$). Otherwise, for any primitive root $\ell$ mod $p$, multiplying the sum by $\ell^m$ permutes the terms modulo $p$ and hence does not change the sum modulo $p$; since $\ell^n \not\equiv 1$ (mod $p$), this is only possible if the sum is zero modulo $p$.