# On a theorem of Hensel about congruence of binomial coefficient

In the paper Binomial coefficients modulo prime powers, Andrew Granville stated the following theorem:

Let $n, m$ and $r=n-m$ be three given positive integer and $p^k$ is the exact power of $p$ dividing $\binom{n}{m}$. Assume that $n=\sum n_ip^i$, $m=\sum m_ip^i, r=\sum r_ip^i$ be representations in base $p$ of $n, m, r$ respectively. Then we have $$\dfrac{1}{p^k}\binom{n}{m}\equiv (-1)^k\left( \dfrac{n_0!}{m_0!r_0!}\right)\left( \dfrac{n_1!}{m_1!r_1!}\right)...\left( \dfrac{n_s!}{m_s!r_s!}\right)\ (\text{mod}\ p)$$

Then later he gave hint but I really don't get it. Could you please give me some hints to prove this theorem? Thanks

$\newcommand{\blfloor}{\bigl\lfloor}$ $\newcommand{\brfloor}{\bigl\rfloor}$

I have found a way to solve this using Granville's hint.

We have $n!=(n!)_pp^{\blfloor\dfrac{n}{p}\brfloor}\big({\blfloor\dfrac{n}{p}\brfloor}\big)!$, hence $$\binom{n}{m}=\dfrac{(n!)_p}{(m!)_p(r!)_p}\dfrac{p^{\blfloor\dfrac{n}{p}\brfloor}}{p^{\blfloor\dfrac{m}{p}\brfloor}p^{\blfloor\dfrac{r}{p}\brfloor}}.\dfrac{\big({\blfloor\dfrac{n}{p}\brfloor}\big)!}{\big({\blfloor\dfrac{m}{p}\brfloor}\big)!\big({\blfloor\dfrac{r}{p}\brfloor}\big)!}.$$ Repeating the above process, we get $$\dfrac{\big({\blfloor\dfrac{n}{p}\brfloor}\big)!}{\big({\blfloor\dfrac{m}{p}\brfloor}\big)!\big({\blfloor\dfrac{r}{p}\brfloor}\big)!}=\dfrac{\big({\blfloor\dfrac{n}{p}\brfloor}!\big)_p}{\big({\blfloor\dfrac{m}{p}\brfloor}!\big)_p\big({\blfloor\dfrac{r}{p}\brfloor!}\big)_p}.\dfrac{p^{\blfloor\dfrac{n}{p^2}\brfloor}}{p^{\blfloor\dfrac{m}{p^2}\brfloor}p^{\blfloor\dfrac{r}{p^2}\brfloor}}\dfrac{\big({\blfloor\dfrac{n}{p^2}\brfloor}\big)!}{\big({\blfloor\dfrac{m}{p^2}\brfloor}\big)!\big({\blfloor\dfrac{r}{p^2}\brfloor}\big)!}.$$

Therefore, by induction, we can claim that $$\binom{n}{m}=\frac{(n!)_p}{(m!)_p(r!)_p}\prod_{i=1}^s\dfrac{\big({\blfloor\dfrac{n}{p^i}\brfloor}!\big)_p}{\big({\blfloor\dfrac{m}{p^i}\brfloor}!\big)_p\big({\blfloor\dfrac{r}{p^i}\brfloor}!\big)_p}.\prod_{i=1}^s\dfrac{p^{\blfloor\dfrac{n}{p^i}\brfloor}}{p^{\blfloor\dfrac{m}{p^i}\brfloor}p^{\blfloor\dfrac{r}{p^i}\brfloor}}.$$

From Granville's paper, we know that $\blfloor \dfrac{n}{p^i}\brfloor-\blfloor \dfrac{m}{p^i}\brfloor-\blfloor \dfrac{r}{p^i}\brfloor=\epsilon_i$, where $\epsilon_i$ is $1$ if there is a carry entering position $i$, and $0$ otherwise. Thus, the third factor in the above product is

$$p^{\sum_{i=1}\left(\blfloor \dfrac{n}{p^i}\brfloor-\blfloor\dfrac{m}{p^i}\brfloor-\blfloor\dfrac{r}{p^i}\brfloor\right)}=p^{\sum_{i=0}^s\epsilon_i};$$

by Kummer's theorem this is the highest power of $p$ dividing $\binom{n}{m}$.

Hence, $$\dfrac{1}{p^k}\binom{n}{m}=\frac{(n!)_p}{(m!)_p(r!)_p}\prod_{i=1}^s\dfrac{\big({\blfloor\dfrac{n}{p^i}\brfloor}!\big)_p}{\big({\blfloor\dfrac{m}{p^i}\brfloor!}\big)_p\big({\blfloor\dfrac{r}{p^i}\brfloor!}\big)_p}.$$

We know that $(-1)^{\blfloor \dfrac{n}{p} \brfloor}(n!)_p\equiv n_0!\ (\text{mod}\ p)$, so $$\dfrac{\big({\blfloor\dfrac{n}{p^i}\brfloor}!\big)_p}{\big({\blfloor\dfrac{m}{p^i}\brfloor}!\big)_p\big({\blfloor\dfrac{r}{p^i}\brfloor!}\big)_p}\equiv (-1)^{\blfloor \dfrac{n}{p^i} \brfloor-\blfloor \dfrac{m}{p^i} \brfloor-\blfloor \dfrac{r}{p^i} \brfloor}\dfrac{n_i!}{m_i!r_i!}=(-1)^{\epsilon_{i}}\dfrac{n_i!}{m_i!r_i!}.$$

Applying this result also the first factor gives $$\dfrac{1}{p^k}\binom{n}{m}\equiv \prod_{i=0}^s (-1)^{\epsilon_{i}}\dfrac{n_i!}{m_i!r_i!}=(-1)^k\dfrac{n_0!}{m_0!r_0!}\dfrac{n_1!}{m_1!r_1!}...\dfrac{n_s!}{m_s!r_s!}.$$

Proof is completed.

• Nice! I made some small edits to put in the factor $n_0!/m_0!r_0!$, which I think was missing from your original version. – Mark Wildon Mar 23 '16 at 12:30

Note. See the great answers by Mark Wildon and alphaomega.

In your notation, Lucas' theorem says that

$$\binom{n}{m}\equiv \binom{[n/p]}{[m/p]}\binom{n_0}{m_0}\ (\text{mod}\ p)$$

According to Granville you just need the identity (mentioned in the paper)

$$(-1)^{[n/p]}(n!)_p \equiv n_0!\ (\text{mod}\ p)$$

By the way, the first proof of this seems to be due to H. Anton (1869).

• I don't follow: Lucas' Theorem is that $\binom{n}{m} = \binom{n_0}{m_0} \binom{n_1}{m_1} \ldots \binom{n_s}{m_s}$ mod $p$. But $n_i!/m_i!r_i!$ is not equal to $\binom{n_i}{m_i}$ in general. (For example, take $n = p$, $m=p-1$, $r=1$.) – Mark Wildon Mar 19 '16 at 12:30
• @Myshkin: Your initial congruence is definitely false as the left hand side is divisible by $p^k$ (by assumption), while the right hand side is clearly not (since each $n_i$ is less than $p$). – GH from MO Mar 19 '16 at 19:37
• @GH from MO: I agree with your new comment, and should not have agreed earlier! (I deleted this comment.) Lucas' Theorem, and its proofs (e.g. the one by polynomials modulo $p$) does seem to require $p$-adic expansions. E.g. $\binom{7}{3} = \binom{2.3+1}{1.3} \equiv \binom{2}{1} \binom{1}{0} \equiv 2 \not\equiv \binom{1}{1}\binom{4}{0}$. – Mark Wildon Mar 19 '16 at 19:51
• @MarkWildon: I also erased my initial remark. Also, as I remarked to Myshkin, his first congruence is in error. Perhaps his factorials need to be replaced by their coprime-to-$p$ parts, but then it is not clear how Lucas's theorem is sufficient. I guess we need to read the original papers. – GH from MO Mar 19 '16 at 20:18

I think I have a bijective proof of an equivalent identity. Here is the special case when $n = n_0 + pn_1 + p^2n_2$, $m = m_0 + pm_1 + p^2m_2$, $r = r_0 + pr_1 + p^2r_2$ and there are carries coming into positions $1$ and $2$, so $n_0 < m_0+ r_0$ and $pn_1 + n_0 < pm_1 + m_0 + pr_1 + r_0$.

Claim. $$\frac{1}{p^2} \binom{n}{m} \equiv \frac{1}{p^2}\binom{m_2+r_2+1}{m_2,r_2,1} \binom{m_1+r_1+1}{m_1,r_1,1} \binom{m_0+r_0}{m_0,r_0} \quad \text{mod p}$$

(Note the final term is the binomial coefficient $\binom{m_0+r_0}{m_0}$ written multinomially.)

By Wilson's Theorem $\frac{x(x-1)\ldots (x-p+1)}{p} \equiv -1$ mod $p$ (this is essentially the identity in Myshkin's answer). Since $m_0+r_0 = n_0+p$, $m_1+r_1+1 = n_1+p$ and $m_2+r_2+1 = n_2$, an equivalent form for the product on the right-hand side is $\frac{1}{p^2} \frac{n_2!}{m_2!r_2!} \frac{n_1!}{m_1!r_1!} \frac{n_0!}{m_0!r_0!}$ as required.

Proof of Claim. Let $P_i$ be a Sylow $p$-subgroup of the symmetric group of degree $p^i$. Thus $P_0$ is a fixed point, $P_1$ is a $p$-cycle and $P_2 = B \ltimes H$ where the base group $B$ is generated by $p$ disjoint $p$-cycles, and $H$ is generated by a permutation of order $p$ permuting these $p$-cycles transitively.

Let $G$ be the direct product of $n_i$ copies of $P_i$, all acting on disjoint subsets of $\{1,\ldots, n\}$. Consider the action of $G$ on $m$-subsets of $\{1,\ldots, n\}$. An $m$-subset is fixed by the action of one of the direct factors if and only if it contains its support. Since $p^2 > m_1p + m_0 > n_1p+n_0$, all orbits have size $\ge p^2$ and $\frac{1}{p^2} \binom{n}{m}$ is congruent, mod $p$, to the number of orbits of size $p^2$.

Let $X$ be an $m$-set in an orbit of $G$ of size $p^2$.

1. There are $m_2$ subgroups $P_2$ with support contained in $X$, and a unique subgroup $P_{2}$ acting non-trivially on $X$. Count these by $\binom{m_2+r_2+1}{m_2,r_2,1}$.

2. Either there is a $p$-cycle in the base group $B$ of this $P_{2}$ acting non-trivially on $X$, or one of the $n_1=m_1p+m_0-p$ $p$-cycles in $G$ acts non-trivially on $X$. In both cases, there are $m_1$ $p$-cycles with support contained in $X$. Count the configurations of $p$-cycles by $\binom{m_1+r_1+1}{m_1,r_1,1}$.

3. The remaining $m_0$ elements of $X$ are either some of the $n_0$ fixed points of $G$, or elements of the distinguished $p$-cycle chosen in 2. (Since $m_0 > n_0$, some elements of the $p$-cycle must be used.) Since $m_0+r_0=n_0+p$, these are counted by $\binom{m_0+r_0}{m_0,r_0}$.

Finally divide by $p^2$ since each orbit of size $p^2$ is counted $p^2$ times by choosing the sets $X$.