proving if a number is prime or not using combinations

Question

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$?

Answer 1

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.

Answer 2

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