# 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, …, mnbe pairwise relatively prime positive integers greater than one anda1, a2, …, anbe arbitrary integers. Then the system of linear congruences

x ≡ a1(mod m1),

x ≡ a2(mod m2),

.

.

.

x ≡ an(mod mn)

has a unique solution modulom =m1*m2*….mn. That is, there is a solutionxwith0≤x<mand 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:**

## Leave a Reply