2
$\begingroup$

I'm looking for a "high school / undergraduate" demonstration for the:

All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ only if $n$ is a power of $p.$

There is a "elementary" (good for high school) demonstration of reciprocal here: http://mathhelpforum.com/number-theory/186439-binomial-coefficient.html

And for this part I'm trying to avoid using more advanced tools like the Theorem of Lucas or Kummer.

Thanks in advance to anyone who can help.

$\endgroup$
  • $\begingroup$ Do I understand correctly that you're looking for a combinatorial demonstration, rather than a proof using the expression for $\binom{n}{i}$? $\endgroup$ – whosleon Jun 24 '14 at 0:12
  • $\begingroup$ Hello Whosleon! No problems in using the expression for $\binom{n}{i}$. But I'm searching for an "easy understanding" demonstration for students of high school. $\endgroup$ – Alex Jun 24 '14 at 0:46
  • $\begingroup$ Sorry, but I have trouble understanding why this is true. Surely $3\mid{10\choose 3}=120$ and $5\mid{26\choose 5}=65780$? $\endgroup$ – Ian Mateus Jun 24 '14 at 0:58
  • $\begingroup$ Hi Ian! Note $0\lt i \lt n$, and 3 not divide $\binom{10}{9} = 10$. $\endgroup$ – Alex Jun 24 '14 at 1:10
  • $\begingroup$ Ian now I understood you. I improved the text. Thanks. $\endgroup$ – Alex Jun 24 '14 at 1:13
3
$\begingroup$

Let $a=p^nk$. Then let $p^m$ be the greatest power of $p$ smaller than or equal to $p^nk$. This number must be strictly smaller than $p^nk$.

Look at $$\binom{p^nk}{p^m}=\frac{ p^nk\cdot(p^nk-1)\cdot(p^nk-2)\dots(p^nk-(p^nk-p^m+1)}{p^m\cdot (p^m-1)\dots 1}$$ The factors on the top form a complete residue class mod $p^m$, as do the elements in the bottom. Therefore we can pair them up so they are congruent mod $p^m$. But since no number less than or equal to $p^nk$ is divisible by $p^ {m+1}$ this gives us all the information to determine the maximum power of $p$ that divides both the top and the bottom, and it is the same. Therefore that fraction is not divisible by $p$.

$\endgroup$
  • $\begingroup$ Hello Bananarama, sorry but I do not understand why you used $i=p^m$ $\endgroup$ – Alex Jun 24 '14 at 0:49
  • $\begingroup$ I use $p^m$ because if $a$ is not a power of $p$ then $\binom{a}{p^m}$ is not a multiple of $p$ $\endgroup$ – Jorge Fernández Hidalgo Jun 24 '14 at 0:51
  • $\begingroup$ Look at the factors on the top and bottom, both are a complete residue class mod $p^m$, notice $p^m$ is the highest power of $p$ between $1$ and $a$. Therefore this tells us the product on top is divisible by $p$ the same amount of times as the product on the bottom, meaning the fraction is not dividible by $p$: $\endgroup$ – Jorge Fernández Hidalgo Jun 24 '14 at 0:58

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.