Lucas' theorem

Lucas' theorem is a mathematical tool used to simplify the calculation of binomial coefficients (combinations) modulo a prime number. It states that to find the binomial coefficient C(n, k) mod p (where p is prime), you can break down n and k into their base-p digits. Then, multiply together the binomial coefficients of these corresponding digits, each taken modulo p, to get the overall result. Essentially, it transforms a complex problem into smaller, easier calculations based on the number's base-p representations.