I am trying to understand the proof of Fleck congruence given in Binomial coefficients modulo prime powers, by A. Granville.

Fleck congruence states that for a prime $p$, integers $n \ge p$ and $0 \le r \le p-1$ and $q=\lfloor \frac{n-1}{p-1}\rfloor$ $$ \sum_{k \equiv r \bmod p}(-1)^k{n \choose k} \equiv 0 \pmod {p^q}.$$

The proof therein is very short and lean but it makes use of algebraic number theory, where my knowledge is very limited.

$\zeta$ being a $p$-th primitive root of $1$, I understand that $$ \sum_{k \equiv r \bmod p}(-1)^k{n \choose k} = \frac{1}{p}\sum_{i=0}^{p-1}\zeta^{-ir}(1-\zeta^i)^n .$$ I also understand that $(1-\zeta^i)^n$ belongs to the ideal generated by $(1-\zeta)^n$, since $\frac{1- \zeta^i}{1-\zeta}=(1+\zeta+\cdot\cdot+\zeta^{i-1})$ which is a unit (inversible) in the ring $\mathbb{Z}[\zeta]$, for $1\le i \le p-1$. It is also clear that $(1-\zeta)^{p-1}=p$. Then I would expect the quotient of $n$ by $p-1$ be involved but I fail to see why the quotient of $n-1$ by $p-1$ is eventually obtained, instead.

Thanks for any clarification.


We have ($i=0$ can be dropped) $$ p\sum_{k\equiv r \ \mathrm{mod} \ p}(-1)^k\binom nk=(1-\zeta)^n\sum_{i=1}^{p-1} \zeta^{-ir}(1+\zeta+\cdots + \zeta^{i-1})^n. \ \ \ \ (1) $$ Writing $\zeta=\zeta-1+1$ and $\zeta^{-ir}=\zeta^{pM-ir}$ for some $M$ with $pM>ir$, we see that $$ \sum_{i=1}^{p-1}\zeta^{-ir}(1+\zeta+\cdots+\zeta^{i-1})^n \equiv \sum_{i=1}^{p-1} i^n \ \mathrm{mod} \ (1-\zeta). $$ The sum on the right is $0$ mod $p$ if $p-1\nmid n$, and $-1$ mod $p$ if $p-1|n$.

Letting $\sum_{k\equiv r \ \mathrm{mod} \ p}(-1)^k\binom nk=X$ and taking norm to (1), we see that $$ p^{p-1} X^{p-1} = p^{n+d}K, \ \ \ (2) $$ where $K\in\mathbb{Z}$, and $\begin{cases} d\geq 1 &\mbox{if } p-1\nmid n \\ d=0 &\mbox{if } p-1|n\end{cases}$.

If $p-1|n$, we have $\frac n{p-1}-1=\left\lfloor \frac{n-1}{p-1} \right\rfloor$ Thus, $\nu_p(X)\geq \left\lfloor \frac{n-1}{p-1} \right\rfloor$.

If $p-1\nmid n$, write (2) in the form of $$ p^{p-1}X^{p-1}=p^{n+d'}K' $$ where $d'\geq 1$ and $(K',p)=1$.

Considering prime factorization of $X$, we obtain $$ p-1+(p-1)\nu_p(X)=n+d', $$ and hence $p-1|n+d'$.

Then $\nu_p(X)=\frac{n+d'}{p-1}-1\geq\left\lfloor \frac{n-1}{p-1} \right\rfloor $.

  • $\begingroup$ I am not familiar with the norm in $\mathbb {Q}(\zeta)$. May I kindly ask you to explain more? $\endgroup$ – René Gy May 9 '20 at 12:31
  • $\begingroup$ Let $c_0, c_1,\ldots, c_{p-1}$ be rational numbers and $\beta=c_0+c_1\zeta^1+\cdots c_{p-1}\zeta^{p-1}$. Then the norm of $\beta$ is denoted by $N(\beta)$ and $$ N(\beta)=\prod_{i=1}^{p-1} (c_0+c_1\zeta^{1i}+\cdots c_{p-1}\zeta^{(p-1)i}). $$ $\endgroup$ – Sungjin Kim May 9 '20 at 12:37
  • $\begingroup$ If $\beta\in\mathbb{Z}[\zeta]$ so that all coefficients $c_0, \ldots, c_{p-1}$ are integers, then $N(\beta)$ is also an integer. $\endgroup$ – Sungjin Kim May 9 '20 at 12:46
  • $\begingroup$ As you would already observed, $N(1-\zeta)=p$. Also, $N(z)=z^{p-1}$ if $z\in\mathbb{Z}$. $\endgroup$ – Sungjin Kim May 9 '20 at 12:49
  • $\begingroup$ Sorry, I need more help: how exactly do you obtain $ N(\sum_{i=1}^{p-1}\zeta^{-ir}(1+\zeta+\cdots+\zeta^{i-1})^n) = K p^d$ ? Also, for $\frac{n+d}{p-1} -1\geq\left\lfloor \frac{n-1}{p-1} \right\rfloor$ to hold when $d \neq 0$, don't we need $d\ge p-2$? $\endgroup$ – René Gy May 10 '20 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.