I am looking for a reference for a proof of the following:


Let $n$ and $a,b, \ldots ,z$ be non-negative integers with $a + b
+ \ldots + z = n$, and let $p$ be a prime. Write $n = n\_0 + n\_1 p + \ldots +
n\_m p^m$ in $p$-ary notation, similarly for $a, b, \ldots , z$.
Then, modulo $p$, the multinomial coefficient ${n \choose a,b, \ldots, z}$ is zero if there is
some "carrying" in computing the sum $a + b + \ldots + z$ (i.e., $a\_i + b\_i + \ldots + z\_i \geq p$ for some $i$). Otherwise, it is the product of the multinomial coefficients of
the individual $p$-digits, that is,


${ n \choose a, b, \ldots, z} = {n\_0 \choose a\_0, b\_0, \ldots, z\_0}{n\_1 \choose a\_1, b\_1,
\ldots, z\_1} \ldots {n\_m \choose a\_m, b\_m, \ldots , z\_m}$


I've found plenty of references for this theorem restricted to *binomial* coefficients, otherwise known as Lucas' theorem, but can't seem to find one for arbitrary multinomials.


Thanks in advance for the help.



Reference needed for Lucas' Theorem for multinomial coefficients modulo a prime
You can prove this by induction on the maximum number of base $p$ digits, and to make the argument simpler it's better to formulate a mildly *stronger* theorem where the leading base $p$ "digit" is allowed to be nonnegative rather than be constrained between 0 and $p-1$: for $d \geq 0$, $t \geq 1$ and nonnegative integers $m\_0,m\_1,\dots,m\_t$, write the $m\_i$'s as
$$
m\_0 = c\_0 + c\_1p + \cdots + c\_dp^d \text{ and } 
m\_j = c\_{0j} + c\_{1j}p + \cdots + c\_{dj}p^d
$$
where $0 \leq c\_i, c\_{ij} \leq p-1$ for $i < d$ and $c\_d \geq 0$, $c\_{dj} \geq 0$. Then 
you want to show 
$$
\binom{m\_0}{m\_1,\dots m\_t} \equiv \binom{c\_0}{c\_{01},\dots,c\_{0t}}\cdots \binom{c\_d}{c\_{d1},\dots,c\_{dt}} \bmod p.
$$
Your description of this result treats separately the case when one of the multinomial coefficients on the right doesn't have a combinatorial meaning (because the numbers in the bottom have a sum exceeding the top), but the congruence is true even in that case if you define a multinomial coefficient as a polynomial in the upper parameter, in the same way you can define $\binom{a}{n}$ as $a(a-1)\cdots(a-n+1)/n!$ in order to give a meaning to $\binom{a}{n}$ even if $a$ is not a positive integer greater than or equal to $n$.


By allowing $c\_d,c\_{d1},\dots,c\_{dt}$ to be just nonnegative, a proof by induction on $d$ immediately reduces to the case $d = 1$. Now use the multinomial theorem in ${\mathbf F}\_p[X\_1,\dots,X\_t]$: in the mod $p$ equation 
$$
(1 + X\_1 + \cdots + X\_t)^{c\_0+c\_1p} = (1 + X\_1 + \cdots + X\_t)^{c\_0}(1 + X\_1^p + \cdots + X\_t^p)^{c\_1}
$$
comparing the coefficient of $X\_1^{m\_1}\cdots X\_t^{m\_t}$ on both sides implies 
$$
\binom{m\_0}{m\_1,\dots m\_t} \equiv \binom{c\_0}{c\_{01},\dots,c\_{0t}}\binom{c\_1}{c\_{11},\dots,c\_{1t}} \bmod p
$$
and we're done.


I gave this argument when I needed the result in www.math.uconn.edu/~kconrad/articles/jacobistick.pdf. See congruence C2 at the bottom of the third page. (Appeared in Enseign. Math. 41 (1995), 141−153.)


