The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 12,067
Registered: 7/15/05
Re: Congruence involving binomial coefficients
Posted: Feb 25, 2013 6:49 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic 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.

>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.


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


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.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

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