April 29, 2022

Lucas Theorem

Kulwinder Kaurkulwinder3213

DURATION

9min

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
import java.lang.*;

class Solution {

  static int nCrModpLasTh(int n, int r, int p) {
    // Base case
    if (r == 0)
      return 1;

    int ni = n % p;
    int ri = r % p;

    return (nCrModpLasTh(n / p, r / p, p) * //recursively calling nCrModpLasTh
      nCrLucasTh(ni, ri, p)) % p;
  }

  //this will return an integer which is remainder of nCr modulus p(prime num)	
  //passing n,r,p arguments where n < p and r < p
  static int nCrLucasTh(int n, int r, int p) {

    int[] arr = new int[r + 1];

    arr[0] = 1; // first row of Pascal Triangle with default value

    for (int i = 1; i <= n; i++) {
      int min = Math.min(i, r);
      for (int j = min; j > 0; j--)

        // (n , j) = (n-1) arr j + (n-1)arr(j-1);
        arr[j] = (arr[j] + arr[j - 1]) % p;
    }
    return arr[r];
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the Test Cases:");
    int t = sc.nextInt();
    //until t is 0
    while (t > 0) {
      System.out.println("\nEnter N:");
      int n = sc.nextInt();
      System.out.println("\nEnter r:");
      int r = sc.nextInt();
      System.out.println("\nEnter p(prime number):");
      int p = sc.nextInt();
      System.out.println(" \n \n Then C(n, r) % p is " + nCrModpLasTh(n, r, p));
      t--;
    }
  }
}

Time Complexity: O(p2 * Log_p N)
Explanation: There are O(Log_pN) digits in base p. Each digit from these numbers will be smaller than p. So calculating each digit takes O(N*N). Hence, the complexity will be O(p² * Log_pN).

Code Snippet:

Variation of Lucas Theorem

Suppose pn is a prime number and m1, n1, m, n and i are non negative numbers with m1, n1 lesser than i. Then, according to Lucas theorem:

This result is based on the proof of Jacobsthal. It is also proved that pn =2 and pn =3 if we replace above ((i-1)/3) by (i/2), and by ((i-1)/2).

Real Use Case and Application of Lucas Theorem

Proof of the Lucas theorem is based on observation. Most common problems can be resolved by the direct implementation of the Lucas theorem. Suppose we want to find the remainder of the binomial coefficient when it is divided by the prime number.