Chinese Remainder Theorem in Java: A Comprehensive Guide

The Chinese Remainder Theorem (CRT) is a powerful tool in modular arithmetic, solving systems of simultaneous congruences. It finds wide applications in number theory, cryptography, and computer science. In this blog, I will explain how CRT works, the underlying principles, and how to implement it in Java with user inputs. We will also explore the importance of the Extended Euclidean Algorithm for computing modular inverses, a critical step in solving CRT.

*Note : In this blog of CRT I am going to use Euclidean Algorithm for solving the chinese reminder theorem.*

But let us understand Chinese Reminder Theorem first.

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem allows us to solve systems of simultaneous congruences with pairwise coprime moduli. Given the following system of congruences:

x ≡ a1 (mod n1) , x ≡ a2 (mod n2) ……….. x ≡ ak (mod nk)

CRT guarantees a unique solution modulo N, where N = n1 * n2 * … * nk, if the moduli n1, n2, …, nk are pairwise coprime, meaning that gcd(ni, nj) = 1 for i not equal to j.

Why Use the Chinese Remainder Theorem?

Let us see why we need to use Chinese Reminder Theorem:

One of the reasons CRT is significant is that it allows us to break down complex modular arithmetic problems into smaller, simpler ones. Instead of working directly with large numbers, we solve multiple smaller equations, and CRT ensures that these smaller solutions lead to a unified answer. This makes CRT useful in optimization problems, cryptographic algorithms like RSA, and various computational applications.

What is the Euclidean Algorithm?

The Euclidean Algorithm is a well-known method for finding the greatest common divisor (gcd) of two numbers. The gcd of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean Algorithm works by iteratively applying the division operation:

gcd(a, b) = gcd(b, a mod b)

until the remainder becomes zero. This gives us the gcd of a and b.

In the context of CRT, the moduli n1, n2, …, nk must be pairwise coprime, meaning gcd(ni, nj) = 1. This property ensures that the modular inverse exists, allowing us to solve the system of congruences.

Why Do We Use the Euclidean Algorithm?

In order to solve the Chinese Remainder Theorem, we must compute a modular inverse. The modular inverse is necessary because it allows us to “reverse” multiplication in modular arithmetic, something that regular division does not handle.

Modular Inverse and Its Role in CRT :

Let’s recall the core formula of CRT:

x = (a1 * N1 * M1 + a2 * N2 * M2 + … ) mod N

Where:

ai is the remainder for the i-th congruence.
Ni = N / ni, where ni is the modulus for the i-th congruence.
Mi is the modular inverse of Ni mod ni.

In this formula, Mi is a number such that:

Ni * Mi is congruent to 1 (mod ni)

Finding Mi, the modular inverse, is crucial for solving CRT, and the best way to compute this modular inverse is through the Extended Euclidean Algorithm.

Why Use the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm goes a step further by not only finding the gcd of two numbers but also expressing that gcd as a linear combination of the two numbers:

a * x + b * y = gcd(a, b)

When gcd(a, b) = 1, the Extended Euclidean Algorithm helps us find x and y, where x is the modular inverse of a mod b. This property allows us to find the number Mi in the CRT formula.

In the context of CRT, for each Ni, we need to find Mi such that:

Ni * Mi is congruent to 1 (mod ni)

This is where the Extended Euclidean Algorithm is used to compute Mi, ensuring that the inverse exists and helping us complete the CRT formula.

Example of the Euclidean Algorithm :

Let’s consider an example to make this clearer. Suppose we need to find the modular inverse of N1 = 35 with respect to n1 = 3.

We solve 35 * M1 is congruent to 1 (mod 3).

Applying the Extended Euclidean Algorithm:

35 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0

Now, we work backwards to express the gcd (1) as a linear combination:

1 = 3 – (1 * 2) 1 = 3 – (1 * (35 – (11 * 3)))

Simplifying this gives us the value of M1 = 2, meaning the modular inverse of 35 modulo 3 is 2.

Implementing Chinese Remainder Theorem in Java

Now as we have understood the concept of Chinese Reminder Theorem and the Euclidean Algorithm Let us implement this using Java

CODE :

import java.util.*;
public class ChineseRemainderTheorem {
    // Function to find the modular inverse of a with respect to mod m using the Extended Euclidean Algorithm
    public static int modularInverse(int a, int m) {
        int m0 = m, t, q;
        int x0 = 0, x1 = 1;
        if (m == 1)
            return 0;
        // Applying extended Euclidean Algorithm
        while (a > 1) {
            q = a / m;
            t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }
        // Make x1 positive
        if (x1 < 0)
            x1 += m0;
        return x1;
    }
    // Function to implement the Chinese Remainder Theorem
    public static int findMinX(int[] num, int[] rem, int k) {
        // Compute product of all numbers
        int prod = 1;
        for (int i = 0; i < k; i++) {
            prod *= num[i];
        }
        // Initialize result
        int result = 0;
        // Applying the formula: x = (a1 * N1 * M1 + a2 * N2 * M2 + ...)
        for (int i = 0; i < k; i++) {
            int Ni = prod / num[i];  // N / num[i]
            int Mi = modularInverse(Ni, num[i]);  // Find Mi which is the modular inverse of Ni mod num[i]
            result += rem[i] * Ni * Mi;
        }
        // Take result mod the product of all moduli
        result = result % prod;
        // If the result is negative, adjust it to be positive by adding prod
        if (result < 0) {
            result += prod;
        }
        return result;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Ask the user for the number of equations
        System.out.print("Enter the number of equations: ");
        int k = scanner.nextInt();
        int[] num = new int[k]; // Moduli array (n1, n2, n3, ...)
        int[] rem = new int[k]; // Remainders array (a1, a2, a3, ...)
        // Input moduli and remainders from the user
        for (int i = 0; i < k; i++) {
            System.out.print("Enter modulus (n" + (i + 1) + "): ");
            num[i] = scanner.nextInt();
            System.out.print("Enter remainder (a" + (i + 1) + "): ");
            rem[i] = scanner.nextInt();
        }
        // Find the minimum x that satisfies all the equations
        int result = findMinX(num, rem, k);
        // Display the result
        System.out.println("The smallest x that satisfies all equations is: " + result);
        // Closing the scanner
        scanner.close();
    }
}

Now let us run this code. [ I have used VS code to run this code].

Input :

Enter the number of equations: 3
Enter modulus (n1): 3
Enter remainder (a1): 2
Enter modulus (n2): 5
Enter remainder (a2): 3
Enter modulus (n3): 7
Enter remainder (a3): 2

Output :

The smallest x that satisfies all equations is: 23

Let us understand the example step by step :

Product of moduli:
- prod = 3 * 5 * 7 = 105
Calculate components for each equation:
- For n1 = 3:
  - N1 = 105 / 3 = 35
  - M1 = modularInverse(35, 3) = 2 (since 35 * 2 ≡ 1 mod 3)
  - Contribution: 2 * 35 * 2 = 140
- For n2 = 5 :
  - N2 = 105 / 5 = 21
  - M2 = modularInverse(21, 5) = 1 (since 21 * 1 ≡ 1 mod 5)
  - Contribution: 3 * 21 * 1 = 63
- For n3 = 7:
  - N3 = 105 / 7 = 15
  - M3 = modularInverse(15, 7) = 1 (since 15 * 1 ≡ 1 mod 7)
  - Contribution: 2 * 15 * 1 = 30
Summing the contributions:
- Total sum: 140 + 63 + 30 = 233
Final result:
- result = 233 % 105 = 23

Feel free to share your thoughts on bit stuffing and how it impacts data communication protocols in the comments below commet box.

Thank You