Number theory

  • Thread starter ehrenfest
  • Start date
  • #1
2,013
1

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

 

Answers and Replies

  • #2
743
1
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
743
1
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
2,013
1
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...
 

Related Threads on Number theory

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
791
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
963
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
925
  • Last Post
Replies
3
Views
1K
Top