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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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)$$

and some elementary number theory. See also Kummer's theorem.

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

  • 3
    $\begingroup$ 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$.) $\endgroup$ – Mark Wildon Mar 19 '16 at 12:30
  • 1
    $\begingroup$ @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$). $\endgroup$ – GH from MO Mar 19 '16 at 19:37
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Mark Wildon Mar 19 '16 at 19:51
  • 1
    $\begingroup$ @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. $\endgroup$ – 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$.


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.