2
$\begingroup$

I was wondering if there was a straightforward proof of the following fact (which I can show is true for specific cases, but not generally):

Let $n$ be composite, and let $p$ be a prime factor $n$. Suppose $p^k$ is the highest power of $p$ that divides $n$. Then the following is true: $\binom{n}{p^k} \ne 0 \pmod p$.

My approach was to see that $\binom{n}{p^k} = \frac{n(n-1)\ldots (n - p^k + 1)}{(p^k)!}$. However, how do I show that $p$ does not divide this quantity? It seems not obvious how to argue that $p$ occurs the same number of times in the numerator as in the denominator.

**Update: ** I am looking for an elementary proof "from scratch" that does not rely on Lucas' Lemma or anything too heavily reliant on field theory. Preferably an argument that pops out from analyzing the binomial coefficient. Thanks!

$\endgroup$

migrated from mathoverflow.net Oct 7 '15 at 2:34

This question came from our site for professional mathematicians.

  • 2
    $\begingroup$ This is a special case of Lucas' lemma and is quite elementary. A quick proof can be obtained by expanding $(x+y)^n$ in characteristic $p$, both the usual way and as $(x^{p^k}+y^{p^k})^{n/p^k}$. $\endgroup$ – Felipe Voloch Oct 6 '15 at 23:57
  • $\begingroup$ I am looking for an elementary proof "from scratch" that does not rely on Lucas' Lemma or anything too heavily reliant on field theory. Preferably an argument that pops out from analyzing the binomial coefficient. Thanks! $\endgroup$ – N. G. Oct 7 '15 at 0:48
  • $\begingroup$ Lucas' theorem en.wikipedia.org/wiki/Lucas%27_theorem pops out from analyzing binomial coefficients. Its proof applied to your particular case will get you "an elementary proof from scratch". $\endgroup$ – Max Alekseyev Oct 7 '15 at 1:22
  • $\begingroup$ There is a combinatorial interpretation (and proof) of the Lucas congruence $\binom{np}{mp} \equiv \binom{n}{m} \mod{p}$. You will easily find it by a google search. Also you could simply compute the exponents of $p$ separately in the numerator and denominator, and see that they are equal. $\endgroup$ – Vesselin Dimitrov Oct 7 '15 at 1:50
  • $\begingroup$ Thanks, @VesselinDimitrov! I am curious, how would you show that the exponents of $p$ are equal in the numerator and denominator? This is really the type of argument I am looking for :) $\endgroup$ – N. G. Oct 7 '15 at 2:04
1
$\begingroup$

We have $${{pm}\choose{pk}}={{m}\choose{k}}\prod_{j=1}^{p-1}\prod_{i=1}^{k}\frac{p(m-k+i)-j}{pi-j},$$ where all fractions in the last product have numerators and denominators coprime to $p$.

$\endgroup$

Your Answer

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