# Trying to understand a proof of Fleck congruence

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$$.

• I am not familiar with the norm in $\mathbb {Q}(\zeta)$. May I kindly ask you to explain more? – René Gy May 9 '20 at 12:31
• 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}).$$ – Sungjin Kim May 9 '20 at 12:37
• 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. – Sungjin Kim May 9 '20 at 12:46
• As you would already observed, $N(1-\zeta)=p$. Also, $N(z)=z^{p-1}$ if $z\in\mathbb{Z}$. – Sungjin Kim May 9 '20 at 12:49
• 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$? – René Gy May 10 '20 at 9:14