Binomial coefficients modulo m
Today I (re)learned that you can compute binomial coefficients C(n,k) = n!/(k! (n-k)!), modulo some integer m, very efficiently. NOT as chatGPT or brave.AI or some stackoverflow people suggest, by computing n! and the denominator (mod m), and then multiply the former by the modular inverse of the latter: That won't work because you will most likely (and certainly for n>m ) get 0 for numerator and probably also the denominator. However, when m is prime, we have the wonderful Lucas's theorem that tells us that C(n,k) = ∏ (C(n[i], k[i] ) ; i=1..L) (mod m) (where ∏ = product) where n[ i ] and k[ i ] are the i -th digits of n and k in base p , and L is the length, i.e., number of base- p digits of k. (For example, { np = digits(n,p), kp = digits(k,p) } in the PARI/GP language.) Remark : In books and Wikipedia, you see the formula with "leading zeros" for k as to get the same length (i.e., L = max{ i...