quasi
Posts:
9,078
Registered:
7/15/05
|
|
Re: Congruence involving binomial coefficients
Posted:
Feb 25, 2013 6:49 AM
|
|
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
|
|
