Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binomial coefficient modulo 2^n

  1. Jun 25, 2006 #1
    I am trying to prove (or find a counterexample for) this:

    Let n be any positive integer, and m any odd integer, with 1 <= m < 2^n. Also, let B(x,y) denote the binomial coefficient, x! /( y! ( x - y )! ). Then

    2^n | B( 2^n , m ).

    Any help is welcome.
  2. jcsd
  3. Jun 25, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    For a fixed n, try induction on m. For the base case B(2^n,1) , you need to be able to count the power of 2 in the prime factorizations of (2^n)! and (2^n-1)!.

    Once you've done that, if it's true for B(2^n,m) consider B(2^n,m+2). Can you relate the number of 2's appearing in m!(2^n-m)! to the number of 2's in (m+2)!(2^n-(m+2))! ?
  4. Jun 26, 2006 #3
    Find the power of 2 in the numerator and denominator of B( 2^n , m ).
    You will find that power of 2 in numerator=2^n - 1
    Power of 2 in denominator=2^n - n - 1
    Hence B( 2^n , m ) is divisible by 2^n.

    Keep Smiling
  5. Jun 27, 2006 #4
    Thanks very much.
    Now I am working on this:
    p | B( p, n ) for all n, 0< n < p, if and only if p is prime.
  6. Jun 27, 2006 #5


    User Avatar
    Science Advisor
    Homework Helper

    B(p,n) divisible by p should be straight forward when p is prime.
    If you're stuck in the other direction, you might want to try looking at some examples to see where it goes wrong if p is composite.
  7. Jun 28, 2006 #6
    This is similar to the previous question.
    Let a be any composite number.
    Let p be a prime factor of a.
    Find the power of p in numerator and denominator. You will arrive at your answer.I would be happy if you tell me about how you proceded in the first question.

    Keep Smiling
  8. Jun 28, 2006 #7
    Back to the first question then, I thought of the following:

    the proposition of 2^n | B(2^n, m) is equivalent to saying that

    2 * 3 * ... * m | (2^n - 1)*(2^n - 2)* ... *(2^n - m + 1), where
    m is odd and m <= 2^{n-1} - 1.

    Take sequence A = 2,3,...,m, and B = 2^n-1, 2^n-2,...,2^n-m+1, then
    A as well as B have m-1 terms.

    2 is a factor of every second term in A, and also of every second term in B, and so 2 divides as many terms in A as in B. Further, 2^k, where k<=n-2, divides every 2^k'th term in A as well as B.

    On the other hand, any prime p <= m is a factor of at least the same number of terms in B as in A, because A and B have the same number of terms, which are ... (I don't remember the right word, but they follow each other with a difference of 1), and 2^n contains no other factor than 2, so B, starting with 2^n-1, should contain all the factors, and their powers, that A contains.

    The way I say it may be clumsy, but I hope it conveys the idea.
    Last edited: Jun 28, 2006
  9. Jun 28, 2006 #8


    User Avatar
    Science Advisor
    Homework Helper

    You don't have to worry about primes other than 2 at all here. The only thing stopping B(2^n,m) from being divisible by 2^n is a possible lack of 2's, so you can just count the number of 2's in 2 * 3 * ... * m and in (2^n - 1)*(2^n - 2)* ... *(2^n - m + 1).

    You can do this by pairing off the even terms (the odds don't matter), eg. when m is 5, you have 2*3*4*5 and (2^n-1)*(2^n-2)*(2^n-3)*(2^n-4). 2 and (2^n-2) both have one 2, 4 and (2^n-4) both have two 2's, similar for the general case. m being odd is important here!
  10. Jun 29, 2006 #9
    Thanks, in fact I realised I needn't have worried about primes other than 2 very soon after posting my comment. However, it's interesting that the fact that, for B( n, m ), m! divides n*(n-1)*...*(n-m+1) is not as obvious as I would have assumed it was.
  11. Jul 3, 2006 #10
    Consider this

  12. Jul 3, 2006 #11
    Thanks, then the only if assumption is obviously wrong, while the if part is trivially obvious.
    Last edited: Jul 3, 2006
  13. Jul 3, 2006 #12


    User Avatar
    Science Advisor
    Homework Helper

    NO!! That is not a counterexample. The "only if" direction is claiming:

    if p|B(p,n) for ALL n where 0<n<p then p is prime

    p=9 does not satisfy p|B(p,n) when n=3. The "for ALL n" is key here. Try the contrapositive for this direction, if p is composite, it's enough to find an n where n does not divide B(p,n).
  14. Jul 3, 2006 #13
    Yes, of course, how can I forget - that exactly was my point!
  15. Jul 3, 2006 #14
    I missed the important phrase 'for all n'
    I am sorry

    Keep Smiling
  16. Jul 3, 2006 #15
    I wonder if this is acceptable as a proof:

    Assume p is composite. Then choose q a prime factor of p, then
    B(p, q) = ( p*(p-1)*...*(p-q+1) ) / ( 2*3*...*q ).
    Now there are q terms in p, p-1, ..., p-q+1, therefore q divides only one of them, which is p. Also, q occurs as a factor of any term in the sequence 2,3,...,q only once. That means that q does not divide B( p, q ), and so p does not divide B( p, q ) if q | p and 1< q < p.
    Last edited: Jul 3, 2006
  17. Jul 3, 2006 #16


    User Avatar
    Science Advisor
    Homework Helper


    Not true. Some power of q may divide p, and q may then divide B(p,q).

    But you're close. Say p=N*q^n, where q does not divide N. You should be able to say the highest power of q that divides B(p,q).
  18. Jul 3, 2006 #17
    Let me try.
    B(p,n)= (p/n)B(p-1,n-1)
    Now, B(p,n) is an inteher for all values of n<=p.
    B(p-1,n-1) is also an intger.
    Now we are given that B(p,n) is divisible by p for all n
    Hence n should not divide p (for any value of n)
    Hence p is a prime

    Keep Smiling
  19. Jul 3, 2006 #18
    I think that the only problem with my proof was saying that q does not divide B(p,q). I would rephrase it this way:

    Assume p is composite, and q is a prime factor of p.
    There are q terms in the sequence p, p-1, ..., p-q+1, therefore q divides only one of them, which is p.
    B(p,q) / p = (p-1)*...*(p-q+1) / q!. As q is not a factor of the numerator, B(p,q)/p is not integral.
  20. Jul 4, 2006 #19


    User Avatar
    Science Advisor
    Homework Helper

    That looks good erszega, nice work.

    I don't see why this follows from what you had.
  21. Jul 4, 2006 #20
    There is some logical inconsistency, leave it.

    However, it has been proved by erszega.

    Keep Smiling
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Binomial coefficient modulo 2^n
  1. Integers Modulo n (Replies: 4)

  2. The Integers Modulo n (Replies: 9)