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

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 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!(k-j)!].
>
>The conjecture is
>
>F(n, g) = 1 (mod q) if g = q + 1 and = 0 (mod q) if not.
>

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 <= n-1 then, letting q = (n-1)/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 = (n-1)/2,
C(n,k) = C(q,k/2) mod 2 for all even integers k with
2 <= k <= n-1.

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 <= n-1, 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 <= n-1,
then C(n,k) is a multiple of n.

Proof:

C(n,k) = (n!)/(k!(n-k)!). The numerator is clearly a multiple
of n, but since n is prime and 1 <= k <= n-1, 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 <= n-1, 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 <= n-1, 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 = (n-1)/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)(2q-1) ... (q+2))/q!

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

Noting that

q+2 = 2 mod q
q+3 = 3 mod q
...
2q-1 = (q-1) mod q

all terms cancel mod q except for the factor 2.

--- (8) corollary

If n is an odd prime such that q = (n-1)/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 = (n-1)/2 is an odd
prime, then A(n,k) = 0 mod q for all even integers k with
2 <= 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.

--- (10) corollary

If n is an odd prime such that q = (n-1)/2 is also an odd prime,
then F(n,k) = 0 mod q for all even integers k with 2 <= k <= q-1.

Proof:

Immediate from lemma (9) together with corollary (6) and the
definition of F(n,k).

--- (11) conclusion

The conjecture is true.

---

quasi

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