HMIC

Solution:
We work in $\mathbb{F}_{p}[X]$.
We claim that
$$(1-4 X)^{\frac{p+1}{2}}-1+2 X^{p}+2 X \sum_{k=0}^{p-1} C_{k} X^{k}=0$$
The solution follows from this claim, as
$$\sum_{k=1}^{p-1} C_{k} n^{k} \equiv 0 \quad(\bmod p) \Longleftrightarrow (1-4 n)^{\frac{p+1}{2}}-1+2 n^{p}+2 n \equiv 0 \quad(\bmod p)$$
Since $n^{p} \equiv n \pmod{p}$, this is equivalent to $n \equiv \frac{1}{4} \pmod{p}$ or $1-4 n$ being a non-zero quadratic residue in $\mathbb{F}_{p}$. But we must omit the solution of $n=0$, so we get $1+\left(\frac{p-1}{2}-1\right)=\frac{p-1}{2}$ values of $n$ that work. Now we prove the claim. Observe the following facts:
- $C_{p-1}=\frac{1}{2p-1}\binom{2p-1}{p}=-1$ by Lucas' theorem.
- For $\frac{p-1}{2}<k<p-1$,
$$\nu_{p}\left(C_{k}\right)=\nu_{p}((2k)!)-\nu_{p}((k+1)!)-\nu_{p}(k!)=1$$
since $k+1<p \leq 2k$, so $C_{k}=0$.
We show that the coefficient of $X^{k}$ in the LHS is 0 for $k=0, \ldots, p$. This is obvious for $k>\frac{p+1}{2}$ and $k=0$ by the above facts, as the coefficient is $2+2 C_{p-1}$ for $k=p$, $2 C_{k}$ for $\frac{p+1}{2}<k<p$, and 0 for $k=0$.
Now for $1 \leq k \leq \frac{p+1}{2}$, the coefficient is $\binom{\frac{p+1}{2}}{k}(-4)^{k}+2 C_{k-1}=0$. Write
$$\begin{aligned} \binom{\frac{p+1}{2}}{k} & =\frac{\frac{p+1}{2} \cdot \frac{p-1}{2} \cdot \frac{p-3}{2} \cdots \frac{p-2k+3}{2}}{k!} \\ & =\frac{\frac{1}{2} \cdot\left(-\frac{1}{2}\right) \cdot\left(-\frac{3}{2}\right) \cdots\left(-\frac{2k-3}{2}\right)}{k!} \\ & =\frac{(-1)^{k-1}}{2^{k}} \cdot \frac{1 \cdot 3 \cdots (2k-3)}{k!} \\ & =\frac{(-1)^{k-1}}{2^{k}} \cdot \frac{(2k-2)!}{2^{k-1}(k-1)!k!} \\ & =-\frac{2 C_{k-1}}{(-4)^{k}} \end{aligned}$$
so the coefficient is 0 .

Solution:
We present an alternate proof of the key claim. Use the same starting facts as before.
Let $Q(X) = -2 + \sum_{k=0}^{\frac{p-1}{2}} C_{k} X^{k} = -2 + X^{p-1} + \sum_{k=0}^{p-1} C_{k} X^{k}$.
Square $Q$ and multiply by $X$ to get
$$\begin{aligned} X Q^{2} & = 4X - 4X \sum_{k=0}^{\frac{p-1}{2}} C_{k} X^{k} + X\left(\sum_{k=0}^{\frac{p-1}{2}} C_{k} X^{k}\right)^{2} \\ & = -4X - 4X Q + X \sum_{k=0}^{p-2} \sum_{j=0}^{k} C_{j} C_{k-j} X^{k} + C_{\frac{p-1}{2}}^{2} X^{p} \\ & = -4X - 4X Q + \sum_{k=0}^{p-2} C_{k+1} X^{k+1} + 4 X^{p} \\ & = -4X - 4X Q + Q + 1 - X^{p-1} + 4 X^{p} \\ & = (1-4X) Q - (1-4X)(X^{p-1} - 1) \end{aligned}$$
It follows that
$$\begin{aligned} 0 & = 4X \cdot \left(X Q^{2} - (1-4X) Q + (1-4X)(X^{p-1} - 1)\right) \\ & = 4X^{2} Q^{2} - 4X(1-4X) Q + 4(1-4X)(X^{p} - X) \\ & = 4X^{2} Q^{2} - 4X(1-4X) Q + (1-4X)^{2} - (1-4X)^{p+1} \\ & = \left(2X Q + (1-4X)^{\frac{p+1}{2}} - (1-4X)\right) \cdot \left(2X Q - (1-4X)^{\frac{p+1}{2}} - (1-4X)\right) . \end{aligned}$$
Evaluating the second factor at 0 gives $-2$, so it is not the zero polynomial. Thus the first factor is the zero polynomial, from which the claim follows.

Solution:
We prove the following generalization: Let $q$ be a power of $p$. Then the polynomial $\sum_{k=1}^{q-1} C_{k} X^{k}$ has $\frac{q+1}{2}$ roots in $\mathbb{F}_{q}$ and $\frac{p+1}{2}$ roots in $\mathbb{F}_{p}$. It once again suffices to prove the key claim, just with $p$ replaced by $q$.
Work in $\mathbb{F}_{q}[[X]]$, the ring of formal power series over $\mathbb{F}_{q}$. Then
$$\begin{aligned} \sum_{k=0}^{\infty} \binom{2k}{k} X^{k} & = (1-4X)^{-\frac{1}{2}} \\ & = (1-4X)^{\frac{q-1}{2}} \left((1-4X)^{q}\right)^{-\frac{1}{2}} \\ & = (1-4X)^{\frac{q-1}{2}} \left(1-4X^{q}\right)^{-\frac{1}{2}} \\ & = (1-4X)^{\frac{q-1}{2}} \sum_{k=0}^{\infty} \binom{2k}{k} X^{qk} \end{aligned}$$
Taking both sides mod $X^{q}$,
$$\sum_{k=0}^{q-1} \binom{2k}{k} X^{k} = (1-4X)^{\frac{q-1}{2}}$$
Then using $\binom{2q}{q} = 2$, we have
$$\sqrt{1-4X} = (1-4X) \cdot (1-4X)^{-\frac{1}{2}} \equiv (1-4X) \cdot \left((1-4X)^{\frac{q-1}{2}} + 2 X^{q}\right) \quad \left(\bmod X^{q+1}\right)$$
so
$$X \sum_{k=0}^{\infty} C_{k} X^{k} = \frac{1-\sqrt{1-4X}}{2} \equiv \frac{1-(1-4X)^{\frac{q+1}{2}} - 2 X^{q}}{2} \quad \left(\bmod X^{q+1}\right)$$
from which the claim follows.
Alternatively, one can also finish by integrating $(1-4X)^{\frac{p-1}{2}}$, noting that the "constant of integration" is no longer a constant but rather a polynomial of the form $a + b X^{p}$.