Chinese Remainder Theorem in Java

Hey guys, in this article we will learn The Chinese Remainder Theorem and implementation it in Java.

The Chinese Remainder Theorem was first introduced by the Chinese mathematician Sun-Tzu in the Sun-Tzu Suan-ching.

Chinese Remainder Theorem

Let m1, m2, …, mn be pairwise relatively prime positive integers greater than one and a1, a2, …, an be arbitrary integers. Then the system of linear congruences
x ≡ a1(mod m1),
x ≡ a2(mod m2),
.
.
.
x ≡ an(mod mn)
has a unique solution modulo m = m1*m2*….mn. That is, there is a solution x with 0≤x<m and all other solutions are congruent modulo m to this solution.

Let’s take an example,
x ≡ 2(mod 3)
x ≡ 3(mod 5)
x ≡ 2(mod 7)

Note: x ≡ a(mod b) means that when we divide x by b then the remainder is a.

From the above example,
m1 = 3, m2 = 5, m3 = 7 ; a1 = 2, a2 = 3, a3 = 2

Step 1: Calculate the value of m where m = m1*m2*m3.
m = 3*5*7 = 105

Step 2: Find M1, M2, M3 where M1 = m/m1, M2 = m/m2, M3 = m/m3.
M1 = 105/3 = 35
M2 = 105/5 = 21
M3 = 105/7 = 15

Step 3: Find y1, y2, y3 which are the modular multiplicative inverses of M1, M2, M3 respectively using the congruence relations give below.
M1*y1 ≡ 1(mod m1)
M2*y2 ≡ 1(mod m2)
M3*y3 ≡ 1(mod m3)
We can find the inverse either by using inspection or the Bézout theorem. Since m1, m2 and m3 in the given example are small values we can go with the inspection method.

• M1*y1 ≡ 1(mod m1)
  35*y1 ≡ 1(mod 3)
  Find a value for y1 such that 0≤y1<3 (m1 = 3) and satisfies the above congruence relation.
  2 seems to satisfy the congruence.
  35*2 ≡ 1(mod 3) ⇒ 70 mod 3 = 1
  ∴ y1 = 2Similarly,
• M2*y2 ≡ 1(mod m2)
  21*y2 ≡ 1(mod 5)
  Find a value for y2 such that 0≤y2<5 (m2 = 5). 1 satisfies the above congruence.
  ∴ y2 = 1
• M3*y2 ≡ 1(mod m3)
  15*y3 ≡ 1(mod 7)
  Find a value for y3 such that 0≤y3<7 (m3 = 7). 1 satisfies the above congruence.
  ∴ y3 = 1

Step 4: Calculate x = (a1*M1*y1 + a2*M2*y2 + a3*M3*y3) mod m
x = (2*35*2 + 3*21*1 + 2*15*1) mod 105 = 233 mod 105 = 23

∴ 23 is the smallest positive integer that satisfies x ≡ 2(mod 3), x ≡ 3(mod 5) and
x ≡ 2(mod 7) simultaneously.

Implementing Chinese Remainder Theorem in Java

Code:

import java.util.*;
class CodeSpeedy{
  static int CRT(int a[], int m[], int n, int p){
    int x = 0;
    
    for(int i = 0; i<n; i++){
      
      int M = p/m[i], y = 0; // M1 = p/m1, M2 = p/m2 ....., Mn = p/mn
      
      for(int j=0; j<m[i]; j++){
        if((M*j)%m[i]==1){
          y = j; break; // Finding the values for y1, y2,..., yn
        }
      }
      
      x = x + a[i]*M*y; // x = a1*M1*y1 + a2*M2*y2 + ... + an*Mn*yn
    }
    
    return x%p; 
  }
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    
    System.out.println("Enter the number of congruence relations: ");
    int size = sc.nextInt();
    
    System.out.println("Enter the values of a: ");
    int a[] = new int[size];
    for(int i=0; i<size; i++)
      a[i] = sc.nextInt();
    
    System.out.println("Enter the values of m: ");
    int m[] = new int[size], p = 1;
    for(int i=0; i<size; i++){
      m[i] = sc.nextInt();
      p = p*m[i]; // p = m1*m2*...*mn
    } 

    System.out.println("The solution is "+CRT(a,m,size,p));
  }
}

Note: This code is efficient only if the values of m1, m2, m3,…., mn are small. For larger values, using the Bézout theorem is recommended.

Output: