Understanding Lucas Theorem: Theory and Code

1. Introduction and Core Concepts

The lucas theorem is one of the most elegant results in combinatorial number theory, providing a powerful method to compute binomial coefficients modulo a prime number when the numbers involved are extremely large. Formally, the theorem states that for non-negative integers n and r and a prime p, the binomial coefficient n choose r modulo p can be expressed as the product of binomial coefficients of the base-p digits of n and r. This deceptively simple statement solves a problem that is otherwise computationally intractable for large values.

To understand why the lucas theorem matters, consider the direct computation of C(n, r) = n! / (r! * (n-r)!). When n is as large as 10^9 or 10^18, which is common in competitive programming and cryptographic applications, calculating factorials directly is impossible due to overflow and time constraints. Even with modular arithmetic, computing n! mod p for such large n is infeasible. The lucas theorem bypasses this by breaking the large problem into many small subproblems where n_i and r_i are less than p, making them easy to compute with precomputed factorials.

The theorem was first proven by the French mathematician Édouard Lucas in 1878. At its core, it connects combinatorics with the representation of numbers in prime bases. The key insight is that the combinatorial structure of choosing r items from n items respects the base-p decomposition. If any digit of r in base p exceeds the corresponding digit of n, the binomial coefficient is immediately zero modulo p. This property alone provides a fast filter for many cases and reveals deep structure about Pascal's triangle modulo a prime, which exhibits fractal-like self-similarity known as Sierpiński's triangle when visualized.

Why Lucas Theorem Is Essential for Large Moduli

In modern computing, we frequently need to compute C(n, r) mod p where p is a relatively small prime (like 10^9+7 is not small, but primes like 2, 3, 5, 7, 1000003 are) and n is enormous. Standard approaches using Fermat's Little Theorem for modular inverses only work when n and r are less than p, because factorial precomputation requires O(p) time and space. The lucas theorem extends this capability to arbitrarily large n and r without increasing the precomputation cost beyond p.

This makes the lucas theorem indispensable in fields that rely on modular combinatorics, including cryptography, error-correcting codes, and randomized algorithms. Without it, many problems requiring efficient computation of large binomial coefficients would require exponential time or be completely unsolvable within practical limits.

2. How It Works

The mechanism of the lucas theorem is rooted in the base-p expansion of integers. Let p be a prime. Any non-negative integer n can be uniquely written in base p as n = n_0 + n_1*p + n_2*p^2 + ... + n_k*p^k where each 0 ≤ n_i < p. Similarly, r = r_0 + r_1*p + r_2*p^2 + ... + r_k*p^k. The lucas theorem then states:

C(n, r) mod p = product_{i=0 to k} C(n_i, r_i) mod p

where we define C(a, b) = 0 if b > a. This means the large binomial coefficient modulo p is simply the product of the small binomial coefficients of the corresponding digits, all taken modulo p.

The proof relies on polynomial identities in the finite field F_p. A classic proof uses the generating function (1 + X)^n and the crucial property that in characteristic p, (1 + X)^p = 1 + X^p mod p. This follows from the fact that C(p, i) is divisible by p for all 0 < i < p. By expanding n in base p and repeatedly applying this identity, we get (1 + X)^n = product (1 + X^{p^i})^{n_i} mod p. Expanding the right side and comparing the coefficient of X^r on both sides yields the theorem. This algebraic perspective shows why primality of p is essential; the binomial coefficients C(p, i) are only guaranteed to be 0 mod p when p is prime.

Intuitive Digit-Wise Independence

Intuitively, the lucas theorem tells us that choosing r objects from n modulo p can be done independently for each base-p digit, with no carries between digits. Think of n and r as numbers in base p. For each digit position, you choose r_i from n_i. If at any position you try to choose more than is available (r_i > n_i), the whole product becomes zero, meaning the overall binomial coefficient is divisible by p. This digit-wise independence is what makes the computation so efficient.

Consider Pascal's triangle modulo p. The theorem explains its fractal structure. For p=2, C(n, r) mod 2 = 1 if and only if every binary digit of r is less than or equal to the corresponding digit of n (i.e., (r & n) == r). This is a well-known bit manipulation trick that is a direct corollary of the lucas theorem.

Requirements and Limitations

The standard lucas theorem strictly requires p to be prime. If p is composite, the identity C(p, i) mod p = 0 fails, and the polynomial proof collapses. For composite moduli, we need more advanced techniques like prime factorization with the Chinese Remainder Theorem, or generalizations such as Lucas theorem for prime powers using Granville's or Andrew's extensions. Understanding this limitation is critical before applying the theorem in practice.

3. Implementation

Implementing the lucas theorem in Python requires two components: a function to compute small binomial coefficients C(n, r) mod p where n, r < p, and a wrapper that applies the digit decomposition. The small case is typically handled using factorials and Fermat's Little Theorem, which states that a^{p-1} = 1 mod p for prime p and a not divisible by p, giving us a^{-1} = a^{p-2} mod p.

The most common implementation precomputes factorials and inverse factorials up to p-1 in O(p) time, allowing O(1) queries for small nCr. For a single query where p is large, we can compute factorials on the fly in O(p) or O(r) time. Below are robust, production-ready implementations.

Helper: Small nCr Mod Prime

# Helper to compute C(n, r) % p for 0 <= n, r < p using Fermat's Little Theorem
# Requires p is prime
def small_nCr_mod_p(n, r, p):
    # If r > n, binomial coefficient is 0
    if r < 0 or r > n:
        return 0
    if r == 0 or r == n:
        return 1
    
    # Optimization: use symmetry C(n, r) == C(n, n-r)
    if r > n - r:
        r = n - r
    
    # Compute n! % p, r! % p, (n-r)! % p
    # For small p, we can compute directly
    numerator = 1
    denominator = 1
    for i in range(1, r + 1):
        denominator = (denominator * i) % p
        numerator = (numerator * (n - r + i)) % p
    
    # Fermat's Little Theorem: a^(p-2) is modular inverse of a mod p
    # Use pow with built-in fast modular exponentiation
    inv_denominator = pow(denominator, p - 2, p)
    return (numerator * inv_denominator) % p

# Alternative with factorial precomputation for multiple queries
def precompute_factorials(p):
    fact = [1] * p
    inv_fact = [1] * p
    for i in range(1, p):
        fact[i] = (fact[i-1] * i) % p
    # Fermat for inverse factorial
    inv_fact[p-1] = pow(fact[p-1], p - 2, p)
    for i in range(p-2, -1, -1):
        inv_fact[i] = (inv_fact[i+1] * (i+1)) % p
    return fact, inv_fact

def small_nCr_with_precompute(n, r, p, fact, inv_fact):
    if r < 0 or r > n:
        return 0
    return (fact[n] * inv_fact[r] % p) * inv_fact[n - r] % p

Core Lucas Theorem: Recursive Implementation

def lucas_recursive(n, r, p):
    """
    Compute C(n, r) % p using Lucas Theorem (recursive version).
    Works for arbitrarily large n, r (up to 10^18) and prime p.
    Time: O(p + log_p(n)) with naive small_nCr, O(log_p(n)) with precomputation
    """
    # Base case: if r == 0, answer is 1
    if r == 0:
        return 1
    
    # Extract last digits in base p
    n_mod_p = n % p
    r_mod_p = r % p
    
    # If r's digit > n's digit, C(n_i, r_i) = 0, so whole result is 0
    if r_mod_p > n_mod_p:
        return 0
    
    # Compute C(n_mod_p, r_mod_p) % p for this digit
    # and multiply by result for remaining digits (n//p, r//p)
    small_comb = small_nCr_mod_p(n_mod_p, r_mod_p, p)
    
    # Recursive call for higher digits
    return (small_comb * lucas_recursive(n // p, r // p, p)) % p

# Example usage:
# print(lucas_recursive(1000, 300, 7))  # Large n, small prime
# print(lucas_recursive(10**18, 10**12, 1000003))  # Very large n

Iterative Lucas with Precomputation for Multiple Queries

def lucas_iterative(n, r, p, fact=None, inv_fact=None):
    """
    Iterative Lucas Theorem - avoids recursion depth issues and is faster.
    Best for handling many queries with same prime p.
    """
    if r < 0 or r > n:
        return 0
    
    # Precompute factorials once if not provided and p is reasonable
    # For p > 10^6, consider on-the-fly computation to save memory
    if fact is None and p < 2000000:
        fact, inv_fact = precompute_factorials(p)
        use_precompute = True
    else:
        use_precompute = fact is not None
    
    result = 1
    while n > 0 or r > 0:
        n_i = n % p
        r_i = r % p
        
        if r_i > n_i:
            return 0
        
        if use_precompute:
            # O(1) lookup
            comb = (fact[n_i] * inv_fact[r_i] % p) * inv_fact[n_i - r_i] % p
        else:
            # O(p) worst case per digit, but no O(p) memory
            comb = small_nCr_mod_p(n_i, r_i, p)
        
        result = (result * comb) % p
        
        n //= p
        r //= p
    
    return result

def lucas_batch(queries, p):
    """
    Process multiple (n, r) queries efficiently for same prime p.
    queries: list of tuples [(n1, r1), (n2, r2), ...]
    """
    # Precompute once for all queries
    fact, inv_fact = precompute_factorials(p) if p < 2000000 else (None, None)
    results = []
    for n, r in queries:
        results.append(lucas_iterative(n, r, p, fact, inv_fact))
    return results

Handling Large Prime Moduli Efficiently

def nCr_mod_p_large_prime_optimized(n, r, p):
    """
    Optimized small_nCr when p is large (e.g., 10^9+7) but n_i, r_i are small.
    Since n_i < p, but r_i may still be up to p-1, we use O(r) method.
    This is ideal when p is large and number of Lucas digits is small.
    """
    if r < 0 or r > n:
        return 0
    if r > n - r:
        r = n - r
    # If r is large (close to p), this is still O(p) which may be heavy
    # In Lucas context, r_i < p, but often r_i is much smaller than p
    result = 1
    for i in range(1, r + 1):
        # result = result * (n - r + i) / i  mod p
        result = result * (n - r + i) % p
        result = result * pow(i, p - 2, p) % p
    return result

def lucas_for_large_p(n, r, p):
    """
    Full Lucas for when p is large (like 10^9+7).
    Note: if n < p, Lucas reduces to single small_nCr call.
    The benefit of Lucas appears when n >= p.
    """
    if r < 0 or r > n:
        return 0
    result = 1
    while n > 0 or r > 0:
        n_i = n % p
        r_i = r % p
        if r_i > n_i:
            return 0
        result = result * nCr_mod_p_large_prime_optimized(n_i, r_i, p) % p
        n //= p
        r //= p
    return result

4. Step-by-Step Example

Let us walk through a concrete example to demystify the lucas theorem. We will compute C(100, 30) mod 7. Directly computing 100! is astronomically large (158 digits), but with the lucas theorem we only need to handle numbers less than 7.

First, we convert n = 100 and r = 30 into base 7. To do this, we repeatedly divide by 7 and record remainders. For 100: 100 / 7 = 14 remainder 2, 14 / 7 = 2 remainder 0, 2 / 7 = 0 remainder 2. Reading remainders in reverse, 100 in base 7 is 202 (since 2*7^2 + 0*7^1 + 2*7^0 = 98 + 0 + 2 = 100). For 30: 30 / 7 = 4 remainder 2, 4 / 7 = 0 remainder 4, so 30 in base 7 is 42. To align digits, we pad with leading zeros: 100 = (2, 0, 2)_7 and 30 = (0, 4, 2)_7.

Now the lucas theorem tells us: C(100, 30) mod 7 = C(2, 0) * C(0, 4) * C(2, 2) mod 7. We evaluate each small binomial coefficient. C(2, 0) = 1. C(0, 4) = 0 because we cannot choose 4 from 0. Since one term is zero, the entire product is zero. Therefore, C(100, 30) mod 7 = 0. This immediately tells us that C(100, 30) is divisible by 7 without ever computing the huge integer.

Detailed Second Example: Non-Zero Result

Let us try another example where the result is non-zero: C(15, 6) mod 5. Convert to base 5. 15 in base 5: 15 / 5 = 3 remainder 0, 3 / 5 = 0 remainder 3, so (30)_5 (since 3*5 + 0 = 15). 6 in base 5: 6 / 5 = 1 remainder 1, so (11)_5 (since 1*5 + 1 = 6). Align to two digits: n = (3, 0)_5, r = (1, 1)_5.

Apply Lucas: C(15, 6) mod 5 = C(3, 1) * C(0, 1) mod 5. Wait, that would be zero again because C(0,1)=0. Let us check our conversion carefully. Actually 15 = 3*5^1 + 0*5^0 is correct, and 6 = 1*5^1 + 1*5^0. So indeed r_0 =1 > n_0=0, so result is 0. Let us pick a better example: C(11, 5) mod 5. 11 in base 5 is (21)_5 because 2*5+1=11. 5 in base 5 is (10)_5. Then C(11,5) mod 5 = C(2,1) * C(1,0) = 2 * 1 = 2 mod 5. We can verify: C(11,5)=462, and 462 mod 5 = 2, which matches.

Algorithmic Walkthrough in Code

Tracing lucas_iterative(11, 5, 5): Iteration 1: n=11, r=5, n_i=1, r_i=0, comb=C(1,0)=1, result=1, n=2, r=1. Iteration 2: n=2, r=1, n_i=2, r_i=1, comb=C(2,1)=2, result=1*2=2, n=0, r=0. Loop ends, return 2. This digit-by-digit process is exactly what the code does, requiring only O(log_p n) iterations. Each iteration works with numbers smaller than p, making it extremely efficient even when n is 10^18 and p is 5, which would have 26 digits in base 5.

5. Complexity Analysis

Understanding the complexity of the lucas theorem is crucial for choosing the right implementation strategy. The overall complexity depends heavily on how we compute the small binomial coefficients C(n_i, r_i) mod p and the size of the prime p relative to n.

The number of digits of n in base p is k = O(log_p n). This is the number of iterations the Lucas loop will perform, whether recursive or iterative. For each digit, we need to compute a small nCr. If we precompute factorials up to p-1, each small nCr is O(1) after O(p) preprocessing. Without precomputation, each small nCr costs O(p) in the worst case (if we compute factorials naively) or O(r_i) if we use the multiplicative formula.

Space complexity is dominated by the factorial tables. Precomputation requires O(p) space to store fact and inv_fact arrays. The iterative Lucas itself uses O(1) auxiliary space besides these tables, while the recursive version uses O(log_p n) stack space. For very large p (e.g., p > 10^7), precomputation becomes infeasible due to memory constraints, and we must switch to the O(r_i) per-digit method which uses O(1) space.

The best case for Lucas occurs when early digit comparison fails (r_i > n_i), allowing immediate return of 0 without processing remaining digits. The worst case requires processing all log_p n digits. In practice, for cryptographic primes like p ≈ 10^9+7 and n ≈ 10^18, log_p n is only 2, so Lucas is extremely fast. For small p like 2 or 3 and large n, log_p n can be 60, but each small nCr is trivial.

Choosing the Right Strategy

If you have many queries with the same p and p < 10^6, precomputation is optimal. The O(p) cost is amortized over many queries. For a single query with large p, avoid precomputation and use the O(r_i) multiplicative method. For p = 2, there is an even faster bit trick: C(n, r) mod 2 = 1 iff (r & ~n) == 0, which is O(1).

6. Variations and Optimizations

The standard lucas theorem is powerful but has limitations that have inspired several important variations and optimizations. The most significant limitation is the requirement that p be prime. When the modulus is a prime power p^q, the standard theorem does not apply directly.

One major optimization is Garner's algorithm combined with the Chinese Remainder Theorem (CRT) for composite moduli. To compute C(n, r) mod m where m is composite, we factor m = p1^a1 * p2^a2 * ... * pk^ak, compute C(n, r) mod pi^ai for each prime power using Lucas generalizations, and then combine the results via CRT. This extends the reach of Lucas-like techniques to any modulus.

For prime powers, the generalization known as Granville's theorem or the Lucas theorem for prime powers uses factorial exponents with p-adic valuations. It involves computing n! with factors of p removed, using concepts like Legendre's formula and Wilson's theorem generalizations. Implementations often use the algorithm by Andrew Granville or the method of Lucas and Wolstenholme, which are more complex but handle cases like C(n, r) mod p^q efficiently for small q.

Precomputation and Caching Optimizations

For competitive programming where many queries share the same p, precomputing factorials and inverse factorials once is the single most effective optimization. Further optimization includes using iterative loops instead of recursion to avoid Python recursion limits and function call overhead. Another trick is to early exit when r_i > n_i, which is common and saves computation.

When p is moderately large (e.g., 10^5 to 10^6) and the number of queries is huge (10^5+), we can also precompute all small nCr values in a 2D table using Pascal's identity C(n, r) = C(n-1, r-1) + C(n-1, r) mod p in O(p^2) time, but this is rarely worthwhile due to quadratic cost. Factorial method remains superior.

Lucas Theorem with Exponentiation and Lucas Sequences

There is also a connection to Lucas sequences, though distinct from the theorem itself. In some contexts, optimizations use fast exponentiation with exponent p-2 via binary exponentiation, which is already optimal at O(log p). Python's built-in pow(base, exp, mod) is implemented in C and is highly optimized, so it should always be preferred over a manual loop.

For extremely small p (like 2, 3, 5), we can use lookup tables for all possible C(n_i, r_i). Since there are only p * p possibilities, this table is tiny and lookups are instant. This is useful in hardware implementations or when processing billions of queries.

7. Real-World Applications

While the lucas theorem originates in pure mathematics, its applications in computer science and engineering are surprisingly broad and practical. Any domain requiring efficient computation of combinatorial counts modulo a prime benefits from it.

In cryptography, many protocols rely on combinatorial properties modulo primes. For example, certain secret sharing schemes and error-correcting codes like Reed-Solomon codes operate over finite fields F_p and require binomial coefficient calculations for encoding and decoding. The lucas theorem allows these operations to scale to large data blocks without overflow.

In competitive programming and algorithmic problem solving, the lucas theorem is a staple for problems involving large combinatorics. Problems like "compute C(n, r) mod p for n up to 10^18" appear frequently on platforms like Codeforces, AtCoder, and in technical interviews at top tech companies. It is also used to count lattice paths, grid traversals, and combinatorial games where the board size is huge but the modulus is small.

Beyond these, the lucas theorem is used in web servers and databases not directly, but indirectly through the algorithms they employ. For instance, consistent hashing and sharding strategies sometimes use combinatorial calculations to estimate collision probabilities. While the direct use in a web server request path is rare, the underlying libraries for hashing, load balancing, and data partitioning may leverage such number-theoretic optimizations for performance.

Network and Database Examples

In network routing, counting the number of distinct paths between nodes in certain topologies can reduce to binomial coefficients. When these counts need to be taken modulo a prime for hashing or verification, Lucas provides the efficient path. In databases, query optimizers that estimate the cardinality of combinatorial joins or permutations may use modular arithmetic to avoid overflow when dealing with large table statistics.

8. Comparison with Alternatives

The lucas theorem is not the only way to compute binomial coefficients modulo a prime. The best method depends on the relative sizes of n, r, and p. Understanding the trade-offs is essential for selecting the right tool for the job.

Direct factorial computation with Fermat's Little Theorem is the simplest alternative. It works well when n < p and p is not too large (so factorial precomputation is feasible). However, it fails completely when n ≥ p because n! mod p = 0 when n ≥ p, making the division undefined (since p divides the factorial, the modular inverse does not exist). Lucas correctly handles this case.

Dynamic programming using Pascal's identity C(n, r) = C(n-1, r-1) + C(n-1, r) can compute C(n, r) mod p in O(n*r) time and O(r) space. This is only feasible for small n (e.g., n < 5000) and is far too slow for large n. It also does not require p to be prime, which is an advantage for composite moduli.

Prime factorization with Legendre's formula is another alternative for computing C(n, r) exactly (without modulo) by counting prime exponents, then taking modulo p at the end. This is useful when you need the exact value or when p is large and n is moderate, but it is inefficient for very large n.

In summary, if n is huge (greater than p) and p is prime and relatively small, the lucas theorem is the undisputed winner. If n < p, direct factorial is simpler and equally fast. If p is composite or n is small, DP or factorization may be more appropriate. For composite p with large n, combine Lucas for prime powers with CRT.

9. Common Mistakes and Best Practices

Implementing the lucas theorem correctly requires attention to several subtle pitfalls that frequently cause bugs, especially in interview and competition settings. One of the most common mistakes is forgetting to check the condition r_i > n_i. Many beginners compute C(n_i, r_i) without this check, leading to incorrect non-zero results when the true answer should be zero. The check must be done for every digit, not just once.

Another frequent error is not handling the case where p is not prime. The standard lucas theorem code will produce wrong answers for composite p without any warning. Always validate that p is prime, or if you must handle composite moduli, implement the CRT-based extension. Similarly, forgetting that factorial precomputation requires O(p) memory can cause memory limit exceeded errors when p is large like 10^9+7. In such cases, do not precompute.

Off-by-one errors in factorial tables are also common. Ensure your factorial array is size p and that you compute inverses correctly using pow(fact[p-1], p-2, p). Using Python's built-in pow with three arguments is critical for performance and correctness; a manual fast exponentiation loop is slower and more error-prone.

Best Practices for Robust Code

Always use the iterative version of Lucas in production Python code to avoid recursion depth limits. Python's default recursion limit is 1000, and while log_p n is usually small, for p=2 and n=10^18, the depth is about 60, which is safe, but iterative is still cleaner and faster.

Precompute factorials once and reuse them for multiple queries. If you are writing a function that will be called many times with the same p, design it to accept precomputed tables as optional arguments, as shown in the implementation section. This can turn an O(q * p) solution into O(p + q log_p n) for q queries.

• Validate inputs: ensure 0 ≤ r ≤ n and p is prime before computation.
• Use symmetry C(n, r) = C(n, n-r) to minimize the loop in small nCr.
• Escape early when r_i > n_i to save time.
• Prefer pow(a, p-2, p) over manual inverse computation.
• Test with small known values: C(5,2)=10 mod 3 =1, C(10,3)=120 mod 7=1.
• For p=2, use the bit trick (r & n) == r for maximum speed.

Finally, document your code clearly. The lucas theorem is not obvious to readers unfamiliar with number theory, so include comments explaining the base-p decomposition and why the product of digit-wise combinations works. This is especially important in team projects and interviews where code readability is evaluated.

10. Interview Questions

Technical interviews frequently test understanding of the lucas theorem through both theoretical questions and coding challenges. Here are common questions and how to approach them.

Q1: Compute C(n, r) mod p for n up to 10^18 and p up to 10^6. How would you do it efficiently?

This is the classic Lucas application. The expected answer is to explain the lucas theorem, describe converting n and r to base p, and computing the product of small combinations using precomputed factorials and Fermat's Little Theorem. The interviewer wants to hear the time complexity O(p + log_p n) and space O(p), and see you handle the r_i > n_i early exit. Be ready to code the iterative version on a whiteboard and discuss why direct factorial fails when n ≥ p.

Q2: Why does Lucas Theorem require p to be prime? What happens if p is composite?

This tests theoretical depth. Explain that the proof relies on C(p, i) mod p = 0 for 0 < i < p, which holds only for prime p. For composite p, e.g., p=4, C(4,2)=6 mod 4 =2 !=0, so the polynomial identity (1+X)^p =1+X^p mod p fails. For composite moduli, you must factor the modulus and use the Chinese Remainder Theorem with prime power extensions. Mentioning Granville's generalization for prime powers shows advanced knowledge.

Q3: How do you compute C(n, r) mod 2 quickly without Lucas?

This is a trick question testing the corollary of Lucas for p=2. The answer is the bit manipulation check: C(n, r) mod 2 =1 iff (r & n) == r or equivalently (r & ~n) ==0. This means every set bit in r must also be set in n. This is O(1) and much faster than general Lucas. Explain that this follows because in base 2, digits are 0 or 1, and C(0,1)=0 so any position where r has 1 and n has 0 makes the product zero.

Q4: What is the time and space complexity of your Lucas implementation? How would you optimize for 10^5 queries with the same p?

Discuss the trade-off between precomputation and per-query cost. With precomputation, total time is O(p + q log_p n) for q queries, space O(p). Without it, time is O(q * p * log_p n) worst case. The optimization is to precompute factorials and inverse factorials once outside the query loop and reuse them. Also mention using iterative over recursive to avoid overhead, and early termination. If p is large (e.g., 10^9+7) and q is large, note that precomputation is impossible and you must use the O(r_i) per-digit method.

Q5: Walk through C(1000, 500) mod 3 using Lucas Theorem.

This tests ability to execute the algorithm manually. Convert 1000 and 500 to base 3. 1000 in base 3 is 1101001 (since 3^6=729, remainder 271, etc.), 500 in base 3 is 200112. Pad to same length and compute product of C(n_i, r_i) mod 3 for each digit. The key is to show systematic base conversion and digit-wise product, and to identify any digit where r_i > n_i leading to zero. Even if you don't finish the arithmetic, demonstrating the process correctly is what interviewers look for.

Mastering these questions requires not just memorizing code, but deeply understanding why the lucas theorem works, when it applies, and how to adapt it to different constraints. Practice implementing it from scratch without reference, and be prepared to discuss its limitations and extensions.