Lucas Theorem
Explore the Lucas Theorem to efficiently compute binomial coefficients modulo a prime number p, using base p digit expansions of integers n and r. Understand the dynamic programming approach to calculating individual subproblems and recursive methods to handle large values, enabling you to solve modular combinations in number theory problems.
We'll cover the following...
We'll cover the following...
Problem introduction
Given three numbers n, r, and p, compute the above value of % p.
Lucas theorem approach
In number theory, the Lucas’ Theorem expresses the remainder of the division of the binomial coefficient by a prime number p in terms of base p expansions of integers n and r.
The Lucas Theorem suggests that the value of ...