quasi
Posts:
10,403
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 = (n1)/2 is an >> odd prime, then A(n,k) = 0 mod q for all even integers k >> with2 <= k <= q1. >> >> Proof outline: >> >> The verification for k = 2 is immediate. Proceeding by >> induction on k, assume k is even with 2 < k <= q1 and >> simplify the difference A(n,k)  A(n,k2). It's not hard to >> show (not hard but a little tedious) that, assuming >> 2 < k <= q1, 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 <= q1, >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 <= q1 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)*...*(2qk+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,k2), as I'd previously suggested.
quasi

