Prove that n divides nCm, if m and n are relaitvely prime

**Timbuk2**

I have to prove that if m and n are relatively prime (i.e. coprime, i.e. gcd(m,n) = 1) then nCm is divisible by n. 0 <= m <= n

Am I missing something obvious here? I wasn't sure how to do this so I went ahead and expanded nCm - to get

[latex]\displaystyle \frac{n(n-1)(n-2)\ldots(n-m+1)}{(m)(m-1)\ldots(1)}[/latex]

Which is clearly divisible by n, as there are no multiples of n in the denominator. I don't really see what relatively prime has to do with it.

Although if n and m are equal, my example doesn't work. Am I taking the completely wrong approach to this?

EDIT: For some reason Latex refuses to display that + sign. That last bracket should be n-m+1

Eliot Rosewater

What might be happening is that in certain cases elements of the denominator are cancelling out that n. For instance, if n=12 and m=4, then (m)(m-1)=12, and this cancels out the n term.

**Timbuk2**

Eliot Rosewater wrote: »

What might be happening is that in certain cases elements of the denominator are cancelling out that n. For instance, if n=12 and m=4, then (m)(m-1)=12, and this cancels out the n term.

Oh yea! That makes perfect sense, I'm not sure what I was thinking! I remember doing an example similar to that, but it was for primes so I don't think there was a danger of them cancelling out.

But if they are relatively prime, then they have no common factors. Using this fact, is my above method somewhat valid?

red_fox

Take for example n=12 m=5 then

[latex]\displaystyle {{12}\choose{5}}:= \frac{12.11.10.9.8}{5.4.3.2.1} [/latex]

So the '12' can be cancelled by '4x3' (of course 12C5 is divisible by 12).

Although if you can assume that the binomial coefficient is always an integer then there is a way to do it which relies only on the point you make.