ChineseRemainderTheorem.java

/* 
import java.util.*;
public class CRT {

    // Function to find the modular inverse using extended Euclidean algorithm
    static int modInverse(int a, int m) {
        int m0 = m, t, q;
        int x0 = 0, x1 = 1;

        while (a > 1) {
            q = a / m;
            t = m;

            m = a % m;
            a = t;

            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }

        if (x1 < 0)
            x1 += m0;

        return x1;
    }

    // Function to find x such that: x ≡ rem[i] mod mod[i]
    static int findMinX(int[] mod, int[] rem, int k) {
        int M = 1;  // Product of all moduli
        for (int i = 0; i < k; i++)
            M *= mod[i];

        int result = 0;

        for (int i = 0; i < k; i++) {
            int Mi = M / mod[i];
            int inverse = modInverse(Mi, mod[i]);
            result += rem[i] * Mi * inverse;
        }

        return result % M;
    }

    public static void main(String[] args) {
        
        Scanner sc=new Scanner(System.in);
        
        int k = sc.nextInt();  // number of equations
        int[] mod = {3, 5, 7};
        int[] rem = {2, 3, 2};
        for (int i = 0; i < k; i++) {
            mod[i] = sc.nextInt();
            rem[i] = sc.nextInt();
        }

        int x = findMinX(mod, rem, mod.length);
        System.out.println("x is: " + x);  // Output should be 23
    }
}

*/

import java.util.*;

public class ChineseRemainderTheorem {
    // Function to find the modular inverse
    private static int modInverse(int a, int m) {
        int m0 = m, t, q;
        int x0 = 0, x1 = 1;

        if (m == 1) return 0;

        while (a > 1) {
            q = a / m;
            t = m;

            // Update m and a
            m = a % m;
            a = t;

            // Update x0 and x1
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }

        // Make x1 positive
        if (x1 < 0) x1 += m0;

        return x1;
    }

    // Function to find the smallest x such that:
    // x ≡ num[i] (mod rem[i]) for all i
    public static int findMinX(int[] num, int[] rem, int k) {
        int prod = 1; // Product of all num[i]
        for (int i = 0; i < k; i++) prod *= num[i];

        int result = 0;

        // Apply the formula: x = Σ (rem[i] * pp * inv)
        for (int i = 0; i < k; i++) {
            int pp = prod / num[i];
            result += rem[i] * modInverse(pp, num[i]) * pp;
        }

        return result % prod;
    }

    public static void main(String[] args) {
        // Example input
        int[] num = {3, 4, 5}; // Moduli
        int[] rem = {2, 3, 2}; // Remainders
        int k = num.length;

        System.out.println("The smallest x is: " + findMinX(num, rem, k));
    }
}