# Binomial sum modulo prime power: Part 1

In the last post we showed that

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$

and then we used Lucas’ theorem to evaluate the sum modulo $p$.

My initial attempt at evaluating the sum was to note that

$(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}$

where $\omega=\exp(2\pi i/p)$, but then I was stuck. Numerical examples suggested that this sum is in fact divisible by $p^{\lceil n/(p-1)\rceil}$, but I could not think of a way of extending the argument from the last post. Nonetheless, some extensive google search recently revealed that

Theorem (Fleck, 1913). For any $j$,

$\displaystyle\sum_{m\equiv j\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\left\lfloor \frac{n-1}{p-1}\right\rfloor}}$.

So taking $j=0$ gives the desired claim after noting that

Fact. $\displaystyle \left\lfloor\frac{n-1}{p-1}\right\rfloor+1=\left\lceil\frac{n}{p-1}\right\rceil$.

Proof. Write $n=q(p-1)+r$ with $0\le r. If $r=0$ then the equation is just $q-1+1=q$, and if $r>0$ then it is $q+1=q+1$. $\square$

This article contains a proof of Fleck’s result using the identity $(*)$. Unfortunately I don’t have a good grasp of the theory behind it.