Name: Tania

Who is asking: Parent
Level: All

really I need somebody help me (another question of my son), how could I demonstrate: nCp is congruent to floor(n/p) (modulo p)? where rCk is a binomial coefficient, rCk = r(r-1)...(r-k+1)/k(k-1)...1, and p is a prime number

I know that X is congruent to Y (modulo z) means the difference X-Y is an integral multiple of X, but I couldn't solve it...

thanks a lot,

Hi Tania,

Anybody with an interest in dividing binomial coefficients must first learn about the theorem of Lucas. It can be found in number theory books and it often appears in math articles. To study nCk you must first write both n and k in base p notation (for any prime p). That is,

n = n0 + n1*p + n2*p2 + ... and
k = k0 + k1*p + k2*p2 + ... .

THEOREM (Lucas) nCk is congruent mod p to the product n0Ck0 * n1Ck1 * ... .

The answer to your question comes from letting k = p in Lucas's theorem:

nCp = n0C0 * n1C1 * n2C0 * ... = n1 (mod p)

On the other hand, Floor [n/p] = n1 + n2*p + n3*p2 + ... = n1 (mod p)

Go to Math Central