Combinations and Primes

[matt000r000]

I need to prove or disprove this statement for extra credit:

If and only if n is a prime number, and r is any number between 1 and n (non-inclusive), then nCr is a multiple of n or is n.

My biggest problem is the prime part. Any strategies, references to previous solutions, or any help whatsoever is greatly appreciated!!

 

[daon]

Maybe if written like this, you'll see what needs to be done:

\(\displaystyle {p \choose k} = p\frac{(p-1)(p-2)\cdots (p-k+1)}{k!}\)

To prove the RHS is an integer multiple of p (if k not 0 or p) might seem daunting, but note that it MUST BE an integer. Think a little bit and you should get it.

 

[matt000r000]

Thank you daon for your help!

Does \(\displaystyle \left(\begin{array}{c} p \\ k \end{array}\right)=_{p}\mbox{C}_{k}\) ? I'm not clear on that. Also, why \(\displaystyle \left( p-k+1 \right)\) ? Where did you get that number?

How you got the rest of it I understand. However, what exactly should I be doing next? The fractional part must be an integer or \(\displaystyle p^{-1}\) . For that to happen, the \(\displaystyle k!\) should be a factor to the numerator. Does the finite product above have k terms? If so, all the terms should cancel out like so: \(\displaystyle \frac{p-a}{a}\) . This would factor each element of the numerator. But how can I prove \(\displaystyle \frac{p-a}{a}\) is always an integer if p is prime? Is this even what I'm supposed to be doing?

I'm sorry, but I just need a little more help.

Any help whatsoever is greatly appreciated!!

 

[daon]

Yes, the choose function may be identified by both of those. I should clarify the notation.

\(\displaystyle _n C_r = {n \choose r} = \frac{n!}{(n-r)!r!} = n\frac{(n-1)!}{(n-r)!r!}\)

I simply cancelled out the (n-r)! when I wrote the numberator like that. It wasn't necessary.

The solution to the problem is actually quite "Easy" once you see it.

We know that if k is not 0 or p \(\displaystyle {p \choose k}\) is an integer other than 1, so why should the following be an integer?

\(\displaystyle \frac{(p-1)!}{(p-k)!k!}\)

Note: NO ARITHEMETIC NEEDED :wink:

 

[matt000r000]

I'm very sorry, but I still don't see it. The top must be an even number (or 1 if p=2, but then the bottom has to be 1 because k=1). The bottom also has to be an even number, due to the fractals. Therefore, two is definitely a factor of both. That's as far as I've been able to get.

All help thus given and all help that can be given is greatly appreciated!

 

[daon]

Sorry, I forgot about this.

p choose n has no numbers in the denominator that divide p (why? because its prime!). Since it is an integer, all the nontrivial factors in the denominator must evenly divide (p-1)!. Thus you get p*k.