\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Putnam 2019 A5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 24}
\maketitle
\section*{Problem}
Let $p$ be an odd prime and define
\[ q(x) = \sum_{k=1}^{p-1} k^{\frac{p-1}{2}} x^k \]
in $\FF_p[x]$.
Find the greatest nonnegative integer $n$ such that
$(x-1)^n$ divides $q(x)$ in $\mathbb{F}_p[x]$.
\section*{Video}
\href{https://www.youtube.com/watch?v=K_YcIS8PW3g&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/K\_YcIS8PW3g}}
\newpage
\section*{Solution}
The answer is $n = \half(p-1)$.
We use derivatives in the following way.
\begin{claim*}
Define $q_0 = q$,
and $q_{i+1} = x \cdot q_i'$.
Suppose $n$ is such that
$q_1$, \dots, $q_{n-1}$ has $x=1$ as a root,
but $q_n$ does not have $x=1$ as a root.
Then $n$ is the multiplicity of $x=1$ in $q$.
\end{claim*}
\begin{proof}
This follows from the fact that $q_{i+1}$
will have multiplicity of $x=1$ one less than in $q_i$.
\end{proof}
On the other hand, we may explicitly compute
\[ q_n(1) = \sum_{k=1}^{p-1} k^{n + \frac{p-1}{2}}. \]
It is a classical fact that the sum of powers vanishes
if and only if $p-1 \nmid n + \frac{p-1}{2}$
(this can be proven by taking a primitive root, say).
The smallest $n$ for which this fails is $n = \frac{p-1}{2}$.
\end{document}