quasi
Posts:
10,677
Registered:
7/15/05


Re: Congruence involving binomial coefficients
Posted:
Feb 24, 2013 6:50 AM


redmond wrote: > >A colleague asked me if the following was true and I can't seem >to give him an answer. Any help would be appreciated. He has a >fair amount of numerical evidence, but just be a victim of the >law of small numbers. > >Let q be an odd prime such that n = 2q + 1 is also a prime. Let >g be an even integer in the interval [2, q + 1]. Finally, let > >F(n, g) = [C(n, g)  nC(q, g/2)]/2n, > >where C(k, j) is the usual binomial coefficient k!/[j!(kj)!]. > >The conjecture is > >F(n, g) = 1 (mod q) if g = q + 1 and = 0 (mod q) if not. > >Thanks in advance,
Yes, the conjecture is true.
For now, I'll just give an outline of the proof.
For readability, I use the letter k instead of g (since g is visually too close to q).
 (1) Definitions
If n is an odd positive integer and k is an even integer with 2 <= k <= n1 then, letting q = (n1)/2, define functions A(n,k) and F(n,k) by
A(n,k) = C(n,k)  n*(C(q,k/2))
F(n,k) = A(n,k)/(2n)
 (2) lemma
If n is an odd positive integer then, letting q = (n1)/2, C(n,k) = C(q,k/2) mod 2 for all even integers k with 2 <= k <= n1.
Proof outline:
Simplify the ratio C(n,k)/C(q,k/2), cancelling common factors and verify that all remaining factors of numerator and denominator are odd.
 (3) corollary
If n is an odd positive integer and k is an even integer with 2 <= k <= n1, then A(n,k) is even.
Proof:
Immediate from lemma (2) and the definition of A(n,k).
 (4) lemma
If n is prime and k is an integer with 1 <= k <= n1, then C(n,k) is a multiple of n.
Proof:
C(n,k) = (n!)/(k!(nk)!). The numerator is clearly a multiple of n, but since n is prime and 1 <= k <= n1, it follows that the denominator is not a multiple of n. But C(n,k) is an integer, hence it must be a multiple of n.
 (5) corollary
If n is an odd prime and k is an even integer with 2 <= k <= n1, then A(n,k) is a multiple of 2n.
Proof:
By lemma (4) and the definition of A(n,k), it follows that A(n,k) is a multiple of n. By corollary (3), A(n,k) is even, hence, since n is odd, A(n,k) is a multiple of 2n.
 (6) corollary
If n is an odd prime and k is an even integer with 2 <= k <= n1, then F(n,k) is an integer.
Proof:
Immeadiate from lemma (5) and the definition of F(n,k).
 (7) lemma
If n is an odd prime such that q = (n1)/2 is also an odd prime, then A(n,q+1) = 2 mod q.
Proof outline:
A(n,q+1) = C(2q+1,q+1)  n*C(q,(q+1)/2)
Since q is an odd prime, C(q,(q+1)/2) = 0 mod q, so
A(n,q+1) = C(2q+1,q+1) mod q.
Expanding C(2q+1,q+1) we get
C(2q+1,q+1)
= C(2q+1,q)
= ((2q+1)(2q)(2q1) ... (q+2))/q!
= ((2*(2q+1))*(2q1) ... (q+2)))/(q1)!
Noting that
q+2 = 2 mod q q+3 = 3 mod q ... 2q1 = (q1) mod q
all terms cancel mod q except for the factor 2.
 (8) corollary
If n is an odd prime such that q = (n1)/2 is also an odd prime, then F(n,q+1) = 1 mod q.
Proof:
Immediate from lemma (7) and the definition of F(n,k).
 (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 with 2 <= 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.
 (10) corollary
If n is an odd prime such that q = (n1)/2 is also an odd prime, then F(n,k) = 0 mod q for all even integers k with 2 <= k <= q1.
Proof:
Immediate from lemma (9) together with corollary (6) and the definition of F(n,k).
 (11) conclusion
The conjecture is true.

quasi

