Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Congruence involving binomial coefficients
Replies: 3   Last Post: Feb 25, 2013 6:49 AM

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: Congruence involving binomial coefficients
Posted: Feb 25, 2013 6:49 AM
 Plain Text Reply

linux wrote:
>quasi wrote:
>>
>> --- (9) lemma
>>
>> If n is an odd positive integer such that q = (n-1)/2 is an
>> odd prime, then A(n,k) = 0 mod q for all even integers k
>> with2 <= k <= q-1.
>>
>> Proof outline:
>>
>> The verification for k = 2 is immediate. Proceeding by
>> induction on k, assume k is even with 2 < k <= q-1 and
>> simplify the difference A(n,k) - A(n,k-2). It's not hard to
>> show (not hard but a little tedious) that, assuming
>> 2 < k <= q-1, the difference is congruent to 0 mod q, hence
>> the truth of the lemma follows from its truth for k=2.

>
>(9)
>
>Note that if q is prime et k is an integer with 2 <= k <= q-1,
>it is easy to prove that Binomial(2q+1,k) an Binomial(q,k) are
>divisible by q without induction. For this, the hypothesis 2q+1
>prime is not necessary.

Actually, for lemma (9), I didn't require 2q+1 to be prime.

But yes, now that I rethink it, lemma (9) is easily proved
without induction. The key idea is the following easy result,
which I'll state as a lemma ...

(8.5) lemma

If q is prime and k is integer with 2 <= k <= q-1 then
C(2q+1,k) is a multiple of q. Moreover, if k is even then
C(q,k/2) is also a multiple of q.

Proof:

C(2q+1,k) = ((2q+1)*(2q)*...*(2q-k+2))/(k!)

Since q is prime, k! is not a multiple of q.

Thus, in the expression above for C(2q+1,k), the numerator is a
multiple of q but not the denominator, hence, since C(2q+1,k) is
an integer, it follows that C(2q+1,k) is a multiple of q.

Similarly, if k is even, the same reasoning shows that
C(q,k/2) is a multiple of q.

Using lemma (8.5), lemma (9) is immediate:

With the hypothesis of lemma (9),

C(n,k) = 0 mod q

C(q,k/2) = 0 mod q

Since

A(n,k) = C(n,k) - n*C(q,k/2)

it follows that A(n,k) = 0 mod q.

So as linux noted, lemma (9) is easily proved without resorting
to induction based on the simplification of A(n,k) - A(n,k-2),
as I'd previously suggested.

quasi

Date Subject Author
2/23/13 Don Redmond
2/24/13 quasi
2/25/13 linux
2/25/13 quasi

© The Math Forum at NCTM 1994-2018. All Rights Reserved.