# All binomial coefficients (n p) are divisible by a prime p only if n is a power of p

#### AlexOlgna

I'm looking for a "high school / undergraduate" demonstration for the:

All the binomial coefficients $\binom{n}{i}$ where $0\lt i \lt n$, are divisible by a prime p only if n is a power of p.

There is a "elementary" demonstration of reciprocal here: http://mathhelpforum.com/number-theory/186439-binomial-coefficient.html

And for this part I'm trying to avoid using more advanced tools like the Theorem of Lucas or Kummer.

Thanks in advance to anyone who can help.

#### JeffM

Re: All binomial coefficients (n p) are divisible by a prime p only if n is a power o

You can't prove it because it is false.

$\dbinom{6}{2} = \dfrac{6!}{(6 - 2)! * 2!} = \dfrac{6 * 5 * 4!}{4! * 2!} = \dfrac{6 * 5}{2} = 15.$

Last I looked, 3 is prime, 15 is divisible by 3, and 6 is not a power of 3 though 6 is an integer multiple of 3.

EDIT: upon reflection, 5 is prime, 15 is divisible by 5, and 6 is not even an integer multiple of 5.

Last edited:
1 person

#### AlexOlgna

Re: All binomial coefficients (n p) are divisible by a prime p only if n is a power o

Hi JeffM, note: "All the binomial coefficients ..... $0\lt i \lt n$". In your example is true for i=1,2,4,5 but is false for i=3.
$3 {\not |} \binom{6}{3}=20$
And yes, is true. You can see the demonstration in lots of websites, I can indicate that for you: http://copper.math.buffalo.edu/urgewiki/uploads/Literature2010Carbonara/Fine47.pdf
But use Lucas Theorem and I'm trying to avoid that.
Regards

Last edited:

#### JeffM

Re: All binomial coefficients (n p) are divisible by a prime p only if n is a power o

Hi JeffM, note: "All the binomial coefficients ..... $0\lt i \lt n$". In your example is true for i=1,2,4,5 but is false for i=3.
$3 {\not |} \binom{6}{3}=20$
And yes, is true. You can see the demonstration in lots of websites, I can indicate that for you: http://copper.math.buffalo.edu/urgewiki/uploads/Literature2010Carbonara/Fine47.pdf
But use Lucas Theorem and I'm trying to avoid that.
Regards
You are correct that I misread the problem. I apologize. I shall think about it, and, presumably, so will others more astute than I.

#### JeffM

Re: All binomial coefficients (n p) are divisible by a prime p only if n is a power o

I am still working. Here is a sketch of where I think I am going.

First, it is easy to prove that n is an integer multiple of p and so p does not exceed n and n $\ge$ 2.

Second, n is obviously a power of p if p = 1 * n.

So the real work involves when p < n.

There exists a unique positive integer z such that $p^{(z - 1)} < n \le p^z.$

Now assume for purposes of contradiction that $n < p^z.$

I suspect it is possible to show that that there is at least one number greater than 1 but less n where all the instances of p in the numerator and in the denominator of the binomial coefficient cancel, which means that the coefficient can be expressed as a product of powers of primes other than p.

I have limited time to work on this so it may take me a while to see if I am able to prove it. (And of course perhaps I won't be able to do so, but if this approach works, it should be comprehensible to high school students.)

#### JeffM

Re: All binomial coefficients (n p) are divisible by a prime p only if n is a power o

I am pretty sure I see a proof for this proposition that would be accessible to high school students, but it would be very lengthy.

The basic idea is that if n is not a power of p then there are necessarily binomial coefficients where the number of integer multiples of p in the numerator equal the number of integer multiples of p in the denominator and so cancel out, leaving a number that is prime relative to p. However, it looks to me that the proof may differ for odd and even p and for odd and even n and require a few lemmas along the way.

1 person