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 = 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) Richard Go to Math Central