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: Number theory

  1. Nov 14, 2007 #1
    1. The problem statement, all variables and given/known data
    How would you prove using number theory that C(n,m) is an integer where n => m =>1? Do you need the Chinese Remainder Theorem? It seems like it should follow easily from what C(n,m) represents but it is hard for me for some reason.

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Nov 14, 2007 #2
    C(n,m) is only an integer under your given restrictions assuming that both n and m are also integers. I assume that you meant to include that as a further restriction?
  4. Nov 14, 2007 #3
    This will follow rather easily if you use a notion from the combinatorial derivation C(n,k).

    That is, if L = the set of ordered k element subsets of {1, 2, ... , n}, then

    |L|= n(n-1)(n-2)...(n-k+1) <- This isn't very hard to show

    Then with a bit more arguing, you can show that

    |L| = C(n,k) * k! which intuitively makes sense since we're saying that the number of ordered sets is the number of unordered sets multiplied by the number of possible orderings.

    (For a more formal argument, actually look up the combinatorial derivation of C(n,k)).

    Thus it's clear that both |L| and k! are integers, and thus it follows that C(n,k) must also be an integer. It's not terribly hard to extend this to a divisibility argument.
  5. Nov 14, 2007 #4
    Yes. I understand how it follows from the combinatorial derivation, but it seems like there should be a number theory proof with modular arithmetic or something...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook