Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By JeffM
  • 1 Post By JeffM

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

  1. #1
    Newbie
    Joined
    Jun 2014
    From
    Miami
    Posts
    2

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

    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: Binomial coefficient

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    826
    Thanks
    418

    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 by JeffM; June 23rd 2014 at 09:49 PM.
    Thanks from AlexOlgna
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2014
    From
    Miami
    Posts
    2

    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/urgew...ara/Fine47.pdf
    But use Lucas Theorem and I'm trying to avoid that.
    Regards
    Last edited by AlexOlgna; June 23rd 2014 at 11:01 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    826
    Thanks
    418

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

    Quote Originally Posted by AlexOlgna View Post
    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/urgew...ara/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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    826
    Thanks
    418

    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.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    826
    Thanks
    418

    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.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime factors and binomial coefficients
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 26th 2011, 11:44 PM
  2. Replies: 1
    Last Post: February 3rd 2011, 07:49 PM
  3. divisible by prime
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 16th 2010, 07:34 PM
  4. Replies: 5
    Last Post: January 1st 2010, 02:59 AM
  5. Replies: 2
    Last Post: May 27th 2009, 10:48 PM

Search Tags


/mathhelpforum @mathhelpforum