Name: Tania
Who is asking: Parent
Question: I know that X is congruent to Y (modulo z) means the difference XY 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 = n_{0} + n_{1}*p + n_{2}*p^{2} + ... and THEOREM (Lucas) nCk is congruent mod p to the product _{n0}C_{k0} * _{n1}C_{k1} * ... . The answer to your question comes from letting k = p in Lucas's theorem: _{n}C_{p} = _{n0}C0 * _{n1}C_{1} * _{n2}C_{0} * ... = n_{1} (mod p) On the other hand, Floor [n/p] = n_{1} + n_{2}*p + n_{3}*p^{2} + ... = n_{1} (mod p) Richard
