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!

Homework Help: A division problem.

  1. May 30, 2009 #1
    1. The problem statement, all variables and given/known data

    the idea is to prove wether a prime 'p' divides the quantities [tex] {p \choose k} [/tex]

    for k=01,2,3,....,p-1

    2. Relevant equations

    3. The attempt at a solution

    i have tried by inspection for small primes 3,5,7,11,13,17,...... but can not guess a simple solution , the idea is to see if for p prime , the Cyclotomic polynomial

    [tex] x^{p}+..........+x+1 [/tex] for p prime.
  2. jcsd
  3. May 30, 2009 #2
    Trying more general circumstances, where p is any prime, we get the simpler question of whether the product (p-1)...(p-n) is divisible by n+1 for all n <= p - 1.
    Ie., for n = 1, we question whether p-1 is divisible by 2, which is trivial. (p-1)(p-2) divisibility by 3 can be seen as well with a little more care.
    There is a basic divisibility theorem about these products that you may have already proven earlier. If not, it is not difficult to prove by a little inspection.
  4. May 30, 2009 #3


    User Avatar
    Science Advisor
    Homework Helper

    Hi zetafunction! :smile:
    If p is prime, how can it not divide pCk (except for k = 0) …

    there's a p on the top, and nothing larger than p-1 on the bottom. :redface:
  5. May 30, 2009 #4
    This question may only be trivial in retrospect. ;) The quotient [itex]\frac{(r-1)!}{(r-k)!k!}[/itex] trivially simplifies to [itex]\frac{(r-1)\cdots(r-k-1)}{k!}[/itex] which depends on k! successfully dividing the product on the top. This is not generally true when r is not prime. Ie., 8 does not divide 8C4.
    It is then up to the OP to show why this is true for primes, but not necessarily composites.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook