1.
Introduction to Lucas Theorem
2.
Calculating (C(N, R) % P) Using Lucas Theorem
3.
C++ Implementation
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024

# Lucas Theorem

Riya
1 upvote

## 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)

## C++ Implementation

Also see, Euclid GCD Algorithm

## FAQs

1. What is the basic idea of Lucas Theorem based approach to calculate C(N, R) % P?
The basic 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 Lucas theorem states:
C(N, R) = (C(N0, R0) * C(N1, R1) * ….. * C(NK-1, RK-1) * C(NK, RK) ) % P

2. Why have we used dynamic programming based function for calculating C(Ni, Ri) % P, where Ni and Ri are the last digits of N and R respectively in base P?
We have used dynamic programming based function because Ni and Ri are smaller than P.

## Key takeaways

This article discussed “Lucas Theorem,” its use to compute the value of (C(N, R) % P) for three given numbers N, R, and P. If you want to solve problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass