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

Jun 2014
2
0
Miami
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.
 
Feb 2014
1,748
651
United States
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:
  • Like
Reactions: 1 person
Jun 2014
2
0
Miami
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:
Feb 2014
1,748
651
United States
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.
 
Feb 2014
1,748
651
United States
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.)
 
Feb 2014
1,748
651
United States
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.
 
  • Like
Reactions: 1 person