# Binomial coefficient modulo 2^n

1. Jun 25, 2006

### erszega

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. Jun 25, 2006

### shmoe

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))! ?

3. Jun 26, 2006

### MalayInd

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

4. Jun 27, 2006

### erszega

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.

5. Jun 27, 2006

### shmoe

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.

6. Jun 28, 2006

### MalayInd

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

7. Jun 28, 2006

### erszega

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
8. Jun 28, 2006

### shmoe

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!

9. Jun 29, 2006

### erszega

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.

10. Jul 3, 2006

### MalayInd

Consider this
9|B(9,2)

KeepSmiling
Malay

11. Jul 3, 2006

### erszega

Thanks, then the only if assumption is obviously wrong, while the if part is trivially obvious.

Last edited: Jul 3, 2006
12. Jul 3, 2006

### shmoe

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

13. Jul 3, 2006

### erszega

Yes, of course, how can I forget - that exactly was my point!

14. Jul 3, 2006

### MalayInd

I missed the important phrase 'for all n'
I am sorry

Keep Smiling
Malay

15. Jul 3, 2006

### erszega

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
16. Jul 3, 2006

### shmoe

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

17. Jul 3, 2006

### MalayInd

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

18. Jul 3, 2006

### erszega

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.

19. Jul 4, 2006

### shmoe

That looks good erszega, nice work.

I don't see why this follows from what you had.

20. Jul 4, 2006

### MalayInd

There is some logical inconsistency, leave it.

However, it has been proved by erszega.

Keep Smiling
Malay