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
 A: 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).
A: $\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.
A: 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$. 


*

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

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

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