Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

a busy cat

I am really confused on this problem. I am given that $p$ = prime number, $1 \leq k \leq p-1$, and am asked to show $\binom{p}{k}$ multiple of $p.$

How do I prove that $\binom{p}{k}$ is a multple of $p$?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

Let $\dbinom{p}{k}=b$.

Then $p!=bk!(p-k)!$.

Note that $p$ divides $p!$ and is relatively prime to $k!(p-k)!$. For it is clear that $p$ cannot divide any number between $1$ and $k$, nor any number between $1$ and $p-k$. It follows that $p$ divides $b$.

Now show that if $p$ is not prime, then the result is not necessarily true. By the way, it is sometimes true: there are plenty of non-prime $p$, and $k$ with $0\lt k\lt p$, such that $p$ divides $\dbinom{p}{k}$.

But I think you are just required to give an example of a non-prime $p$, and a $k$ with $0\lt k\lt p$, such that $p$ does not divide $\dbinom{p}{k}$. A little fooling around will yield an example.

Remarks: $1.$ Here is a cute combinatorial proof of the result about primes. There is a circular table, with $p$ chairs symmetrically placed around the table. There are $\dbinom{p}{k}$ ways to choose $k$ chairs for $k$ people to sit on. Call two choices equivalent if one can be obtained from the other by moving everybody counterclockwise by the same amount $a$, where $0\le a\le p-1$. Then every seating belongs to a unique equivalence class of size $p$. It follows that $p$ must divide the number of ways to seat the people.

$2.$ From the wording of the question, it is possible that you are supposed to show that for every non-prime $m\gt 1$, there is a $k$ with $0\lt k\lt m$ such that $\dbinom{m}{k}$ is not divisible by $m$. This takes some effort to prove.

share|improve this answer

Re: prove that this is not true if $p$ is not prime.

Well, it is (vacuously) true if $p=1$. But if $p>1$ is not prime, let $q$ be a prime that divides $p$. If $q^d$ is the highest power of $q$ that divides $p$, show that $q^d$ does not divide $p \choose q$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.