# Number theory

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

## The Attempt at a Solution

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?

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.

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