elementary number theory - Prove something is divisible by a prime

Let $p$ be a prime. Prove that $\sum_{k=j}^{p-1} \frac{k!}{ j! (k-j)! }$ is divisible by $p$ $\forall$ $j \in \{0, ..., p-2\}$.

Where this problem comes from:

• I am trying to prove that $1+x+\dots+x^{p-1}$ is irreducible over $\mathbb{Q}[x]$ where $p\in\mathbb{P}$.


• I concluded that it would be the same to prove that $1+(x+1)+\dots+(x+1)^{p-1}$ is irreducible over $\mathbb{Q}[x]$.


• I wrote out the latter polynomial as $\sum_{j=1}^{p-1}\sum_{k=j}^{p-1}\frac{k!}{j! (k-j)!}x^j$ and set out to employ the Eisenstein criterion.

What I've tried so far:

• Induction on $j$. The $j=0$ case is easy as the coefficient is just $p$.


• Assuming it is true for some $j\in\{0,\dots,p-3\}$, I wrote out $\sum_{k=j+1}^{p-1}\frac{k!}{(j+1)!(k-j-1)!}$ and tried to express it as things that are obviously divisible by $p$ and the $j$ term to no avail.

Answer

In this answer, two proofs are given of
$$
\sum_{j=m}^{n}\binom{j}{m}=\binom{n+1}{m+1}
$$
Therefore,
$$
\sum_{k=j}^{p-1}\binom{k}{j}=\binom{p}{j+1}
$$

Now, if $j\lt p-1$, $\binom{p}{j+1}=\frac{p(p-1)\cdots(p-j)}{(j+1)!}$ has a factor of $p$ in the numerator and no factor of $p$ in the denominator. Therefore,
$$
\left.p\,\middle|\,\sum_{k=j}^{p-1}\binom{k}{j}\right.
$$