Name: Tania

Who is asking: Parent
Level: All

Question:
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,
Tania

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 = n₀ + n₁*p + n₂*p² + ... and
k = k₀ + k₁*p + k₂*p² + ... .

THEOREM (Lucas) nCk is congruent mod p to the product _n0C_k0 * _n1C_k1 * ... .

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

_nC_p = _n0C0 * _n1C₁ * _n2C₀ * ... = n₁ (mod p)

On the other hand, Floor [n/p] = n₁ + n₂*p + n₃*p² + ... = n₁ (mod p)