1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binomial Coefficient of a Prime Power

  1. Nov 23, 2014 #1
    1. The problem statement, all variables and given/known data
    Let p be a prime, k be positive integer, and m ∈ {1, 2, 3, ..., pk-1}. Without using Lucas' theorem, prove that p divides [itex]\binom{p^k}{m}[/itex].
    2. Relevant equations
    The definition of the binomial coefficients: [itex]\binom{a}{b} = \frac{a!}{b! (a-b)!}[/itex]

    3. The attempt at a solution
    I've managed to prove the statement when k=1 by arguing that p must divide p! but cannot possible divide m!(p-m)!. I figure I should be able to use a similar counting argument for this proof, likely by counting the number of factors of p that appear in the numerator and in the denominator of [itex]\binom{p^k}{m}[/itex]. It looks to me as though the number of factors of p in [itex]p^k ![/itex] is [itex]\sum_{i=1}^{k} p^{k-i}[/itex]. However, I'm having applying this to the problem. If anyone could give some advice on how to do so, or perhaps nudge me in the direction of a different proof it would be much appreciated.

    Last edited: Nov 23, 2014
  2. jcsd
  3. Nov 24, 2014 #2


    User Avatar
    2017 Award

    Staff: Mentor

    That counting argument should work. You can can find a similar formula for m! and (pk-m)! and try to evaluate the difference.

    Or directly consider the fraction as
    $$\frac{p^k \cdot (p^k-1) \cdot \dots}{m! \cdot (m-1)! \cdot \dots}$$ and try to find matching factors there. Hmm... induction over m?
  4. Nov 24, 2014 #3
    Thanks for the help. I followed your advice and worked out similar formulas for m! and for (pk-m)!, and managed to prove the result by bounding the difference using geometric series. I appreciate your comment, it gave me the little push in the right direction that I needed.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted