Lucas Theorem

Problem introduction

Given three numbers n, r, and p, compute the above value of $\binom{n}{r}$% p.

Lucas theorem approach

In number theory, the Lucas’ Theorem expresses the remainder of the division of the binomial coefficient $\binom{n}{r}$ by a prime number p in terms of base p expansions of integers n and r.

The Lucas Theorem suggests that the value of $\binom{n}{r}$ can be computed by multiplying results of $\binom{n_{i}}{r_{i}}$ where $n_{i}$ and $r_{i}$ are individually same-positioned digits in base p representations of n and r respectively. The idea is to one by one compute $\binom{n_{i}}{r_{i}}$ for individual digits $n_{i}$ and $r_{i}$ in base p.

Let us now look at how this solution can be implemented.