The Chinese Remainder Theorem (CRT) is a theorem that gives a unique solution to simultaneous linear congruences with co-prime moduli. In its basic form, the CRT will determine a number that, when divided by some given divisors, leaves given remainders.

Suppose are positive integers that are pairwise co-prime. Then for any given sequence of integers , there exists an integer solving the following system of simultaneous congruences:

CPP CODE:

#ifndef ONLINE_JUDGE
#define DEBUG true
#endif
#ifndef DEBUG
#define DEBUG false
#endif

#include <iostream>
using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;

#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define Yes cout << "Yes" << endl
#define endl '\n'
const ll INF = 1e9;
const int MOD = 1e9 + 7;
const int MAXN = 2e5;

int main() {
    int a1=0, a2=0, a3=0, n1, n2, n3, i, j, k, hcf1, hcf2, hcf3, N, Y;

    cout << "Enter list of remainders: " << endl;
    cin >> a1 >> a2 >> a3;

    cout << "Enter list of modulos: " << endl;
    cin >> n1 >> n2 >> n3;

    if (n1 * n2 * n3 == 0) {
        cout << "Invalid input of modulo.";
        return 0;
    }

    //check the HCF for pairs:
    //(n1, n2) 
    for (int i = 1; ((i < n1) || (i < n2)); i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            hcf1 = i;
        }
    }

    //(n1, n3)
    for (int j = 1; ((j < n1) || (j < n3)); j++) {
        if (n1 % j == 0 && n3 % j == 0) {
            hcf2 = j;
        }
    }

    //(n2, n3)
    for (int k = 1; ((k < n2) || (k < n3)); k++) {
        if (n2 % k == 0 && n3 % k == 0) {
            hcf3 = k;
        }
    }

    if ((hcf1 != 1) || (hcf2 != 1) || (hcf3 != 1)) {
        cout << "n1 n2 n3 are not pairwise co-prime.";
        return 0;
    }

    cout << "The system of congruences to be solved is: " << endl;
    cout << "x % " << n1 << " = " << a1 << endl;
    cout << "x % " << n2 << " = " << a2 << endl;
    cout << "x % " << n3 << " = " << a3 << endl;

    N = n1 * n2 * n3;
    int m1 = N / n1, m2 = N / n2, m3 = N / n3;
    int mi1 = m1 % n1, mi2 = m2 % n2, mi3 = m3 % n3;
    Y = (a1 * m1 * mi1) + (a2 * m2 * mi2) + (a3 * m3 * mi3);
    Y %= N;

    cout << "The system of congrences has the solution " << Y << " modulo " << N << endl;
    return 0;
}