# Number theory

1. Nov 14, 2007

### ehrenfest

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. Nov 14, 2007

### 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?

3. Nov 14, 2007

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

4. Nov 14, 2007

### ehrenfest

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