, 2006

We observe that
$$A = \sum_{r \ge 0,\ r\ \text{even}} \binom{n}{rp} \frac{(rp)!}{(p!)^r r!}$$
and
$$B = \sum_{r \ge 0,\ r\ \text{odd}} \binom{n}{rp} \frac{(rp)!}{(p!)^r r!}$$
The empty collection corresponds to $r=0$ in the summation for $A$. If $u_r = \frac{(rp)!}{(p!)^r r!}$, $r \ge 0$, then we have
$$u_{r+1} = \frac{(rp+1)(rp+2)\cdots}{ }$$
Hence we obtain
$$(p-1)!\, u_{r+1} = (rp+1)(rp+2)\cdots (rp+p-1) u_r.$$
Reading this modulo $p$, we get $u_{r+1} \equiv u_r \pmod{p}$, $r \ge 0$. Using $u_0 = 1$, we conclude that $u_r \equiv 1 \pmod{p}$, for all $r \ge 1$. This implies that
$$A - B \equiv \sum_{r \ge 0} (-1)^r \binom{n}{rp} \pmod{p}.$$
Thus we need to show that $p$ divides $M = \sum (-1)^r \binom{n}{rp}$. Suppose $p$ is odd. Taking $f(x) = (1-x)^n$, and $\omega$ to be a primitive $p$-th root of unity, we see that
$$\begin{align*} \sum_{k=0}^{p-1} f(\omega^k) &= \sum_{k=0}^{p-1} (1 - \omega^k)^n \\ &= \sum_{k=0}^{p-1} \sum_{j=0}^{n} \binom{n}{j} (-1)^j \omega^{kj} \\ &= \sum_{j=0}^{n} \binom{n}{j} (-1)^j \sum_{k=0}^{p-1} \omega^{kj}. \end{align*}$$
We observe that
$$\sum_{k=0}^{p-1} \omega^{kj} = \begin{cases} \frac{1-\omega^{pj}}{1-\omega^j} = 0 & \text{if } p \text{ does not divide } j \\ p & \text{if } p \text{ divides } j. \end{cases}$$
Thus the above sum reduces to
$$p \left\{ \binom{n}{0} - \binom{n}{p} + \binom{n}{2p} + \dots \right\} = pM.$$
However $1, \omega, \omega^2, \dots, \omega^{p-1}$ are the roots of $x^p - 1 = 0$. If we set $\alpha_k = 1 - \omega^k$, $0 \le k \le p-1$, then $\alpha_0, \alpha_1, \dots, \alpha_{p-1}$ are the roots of $(x-1)^p+1 = 0$. If we set $c_j = (-1)^j \binom{p}{j}$ for $j = 1, 2, \dots, p-1$, then we have
$$(x-\alpha_0)(x-\alpha_1)(x-\alpha_2)\cdots(x-\alpha_{p-1}) = x^p+c_1x^{p-1}+c_2x^{p-2}+\cdots+c_{p-1}x+c_p$$
where we take $c_p = 0$. We observe that $p$ divides $c_j$ for $0 \le j \le p-1$. Taking $s_k = \sum_{j=0}^{p-1} \alpha_j^k$, use of Newton's identities show that $s_k$ is divisible by $p$ for $k \ge 0$. Moreover for $n \ge p$, we also have
$$s_n + c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_{p-1} s_{n-(p-1)} + c_p s_{n-p} = 0.$$
Thus $p^2$ divides $s_n$. But
$$s_n = \sum_{j=0}^{p-1} \alpha_j^n = \sum_{j=0}^{p-1} (1 - \omega^j)^n = pM.$$
It follows that $p$ divides $M$.
If $p$ is even, then $M \equiv \sum_{j \ge 0} \binom{n}{2j} \equiv 2^{n-1} \pmod{2}$. Since $n \ge p=2$, we conclude that $2$ divides $M$.