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<p-1. 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.



Filed under Number theory

2 responses to “Binomial sum modulo prime power: Part 1

  1. Pingback: Proof of binomial sum fact | Samin Riasat's Blog

  2. Ailish! I was thinking of you not long ago and how wonderful our little group was when you were at the helm. I hope you are well. Thank you for your kind words. I miss the kids and need to hop the train and see if any of them are still around. I miss Derrick, too. What a sweet soul he was.Much lor,vBaebara

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s