**Introduction to Lucas Theorem**

This blog will discuss ‘Lucas Theorem”. If we have three numbers N, R, and P and we have to find the value of ( C(N, R) mod P), Lucas Theorem can be used to compute the asked value. Here C(N, R) is the binomial coefficient.

**Statement of Lucas Theorem:**

If ‘N’ and ‘R’ are two non-negative integers and ‘P’ is a prime number, then the following relation is true:

C(N, R) = (C(N0, R0) * C(N1, R1) * ………….. * C(NK-1, RK-1) * C(NK, RK) ) % P

where,

N = NKPK + Nk-1PK-1 + …… + N1P + N0

R = RkPK + Rk-1PK-1 + …… + R1P + R0

In the next section, we will see how we can use Lucas Theorem for calculating (C(N, R) % P) for three given numbers, ‘N,’ ‘R,’ and ‘P.’

**Calculating (C(N, R) % P) Using Lucas Theorem**

This section will discuss how to calculate the value of (C(N, R) % P) for three given numbers, N, R, and P, using the Lucas Theorem. The idea is to one by one calculate the values of C(Ni, Ri) in base P and then compute (C(N, R) % P) using these values as per the Lucas Theorem.

In the function to calculate (C(N, R) % P), first write the base case that if r =0, return 1. Then calculate the last digits of N and R in base p and call the function recursively to calculate the value of (C(N/P, R/P) % P) and for the last digits call dynamic programming based function to calculate (C(Ni, Pi)%P), where Ni and Ri are last digits of N and R respectively in base P. Then multiply these two results to get the final value of (C(N, R) % P).

Please note that we have used a dynamic programming based function for calculating the value of (C(Ni, Ri)%P) for the last digits of N and R in base P because they will be smaller than P. In the dynamic programming approach, we will create an array “C[]” of size R+1, where C[i] stores the value of C(N, i) for i=0 to i=R. Then create a “for loop,” and one by one fill the array “C[]” using the recurrence relation:

C(N, i) = C(N-1, i) + C(N-1, i-1)