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

    shmoe

    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
    Malay
     
  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

    shmoe

    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
    Malay
     
  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

    shmoe

    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
    9|B(9,2)

    KeepSmiling
    Malay
     
  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

    shmoe

    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
    Malay
     
  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

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    True.

    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
    Malay
     
  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

    shmoe

    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
    Malay
     
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)

Loading...