Who is asking: Parent
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,
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
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