1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ See Lucas's Theorem. $\endgroup$
    – Mayank Pandey
    Commented Jul 2, 2015 at 1:24
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 2, 2015 at 1:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Commented Jul 2, 2015 at 1:28
  • $\begingroup$ Right, Lucas' theorem yields it immediately. The proof below is good, too. Thanks everyone. $\endgroup$
    – David Handelman
    Commented Jul 2, 2015 at 2:00

2 Answers 2

Reset to default
6
$\begingroup$

Sorry, don't know a reference, but here is a quick argument.

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.

Improve this answer
$\endgroup$
0
0
$\begingroup$

As for references, you may want to give a look at the introduction and Section 2.2 of R. Meštrović's survey/preprint on Lucas's theorem (on arXiv).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .