Proving C(n,m) is an Integer: Number Theory & Chinese Remainder Theorem?

[ehrenfest]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

 

[Kreizhn]

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?

 

[Kreizhn]

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.

 

[ehrenfest]

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?

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...