# binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result.

Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive integer, we have $${{M} \choose {p^a}} \equiv {\rm floor}\left(\frac M{p^a} \right) \mod p.$$ [The thing on the left is supposed to represent $M$ choose $p^a$, and the right side is supposed to be the floor of $M/p^a$, but on my screen, it looks confusing.]

I have a tedious argument for this (which is probably correct), but why re-invent the binomial wheel? This identity must be known. Can someone provide a reference?

• See Lucas's Theorem. Jul 2, 2015 at 1:24
• Do you know of Kummer's theorem (or Lucas's theorem) on binomial coefficients? I think it would be a consequence of one of those. Gerhard "Don't Have A Literature Reference" Paseman, 2015.07.01 Jul 2, 2015 at 1:25
• If p^a divides M, this is easy. Just let C_M be the cyclic group of order M and let G be the p^a element subgroup. Then G acts on the p^a element subsets if C_M and the fixed points of G are its cosets. So it follows from the fact that the number of fixed points of a p-group acting on a set is congruent to the size of the set mod p. I don't know if this idea can be adapted to the general case. Jul 2, 2015 at 1:28
• Right, Lucas' theorem yields it immediately. The proof below is good, too. Thanks everyone. Jul 2, 2015 at 2:00

If $M=p^ab+c$ with $0\leq c\leq p^a-1$, then $$(1+x)^M=(1+x)^{p^ab}(1+x)^c =(1+x^{p^a})^b(1+x)^c \mod p.$$ In turn, this equals $$(1+bx^{p^a} + ...)(1+x)^c \mod p$$ where $...$ means higher degree terms. Since $c<p^a$, there is no further correction after multiplying by $(1+x)^c$ (the coefficient by $x^{p^a}$ stays $b$), and you are done.