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:

PSEUDO CODE:

Declare a1, a2, a3, n1, n2, n3, i, j, k, hcf1, hcf2, hcf3, N, and Y.

Ask the user politely to input list of three remainders and list of three modulos, respectively.

Check for the input value of n1, n2, and n3. 
	If n1 or n2 or n3 equal to 0,
	Output “Invalid input of modulo.”;
		Terminate;
Otherwise,
Check for the highest common factor (hcf) for the following pairs: (n1, n2), (n1, n3), and (n2, n3).
For pair (n1, n2), initialize i = 1; i less than n1 or i less than n2; i increased by one. 
If n1 % i = 0 and n2 % i = 0,
	hcf1 = i;
For pair (n1, n3), initialize j = 1; j less than n1 or j less than n3; j increased by one. 
If n1 % j = 0 and n3 % j = 0,
	hcf2 = j;

For pair (n2, n3), initialize k = 1; k less than n2 or k less than n3; k increased by one. 
If n2 % k = 0 and n3 % k = 0,
	hcf3 = k;
	
If hcf1 not equal to 1 or hcf2 not equal to 1 or hcf3 not equal to 1,
 Output “n1 n2 n3 are not pairwise co-prime.”;
    	Terminate;

Output “The system of congruences to be solved is:”
Output x % n1 = a1;
Output x % n2 = a2;
Output x % n3 = a3;

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

Output “The system of congruences has the solution Y modulo N”;

Terminate;
// end of pseudocode

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;
}