Binomial coefficient modulo 2^n

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

 

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

 

[MalayInd]

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.

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

 

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

 

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

 

[MalayInd]

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.

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

 

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

 

[shmoe]

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.

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!

 

[erszega]

Thanks, in fact I realized 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.

 

[MalayInd]

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.

Consider this
9|B(9,2)

KeepSmiling
Malay

 

[erszega]

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

 

[shmoe]

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

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

 

[erszega]

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

 

[MalayInd]

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

Keep Smiling
Malay

 

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

 

[shmoe]

Now there are q terms in p, p-1, ..., p-q+1, therefore q divides only one of them, which is p.

True.

Also, q occurs as a factor of any term in the sequence 2,3,...,q only once.

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

 

[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

 

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

 

[shmoe]

That looks good erszega, nice work.

Hence n should not divide p (for any value of n)

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

 

[MalayInd]

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

There is some logical inconsistency, leave it.

However, it has been proved by erszega.

Keep Smiling
Malay