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?

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

2 Answers 2

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.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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