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
    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
    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
    Jul 2, 2015 at 1:28
  • $\begingroup$ Right, Lucas' theorem yields it immediately. The proof below is good, too. Thanks everyone. $\endgroup$
    – David Handelman
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.