#include <iostream.h>
#include <Integer.h>
#include "euclid.h"
#define MAXLEN 500
Integer CRT(Integer a[], Integer m[], int tuplesize);


main (){
    Integer ai, a[MAXLEN] , m[MAXLEN] , x, M=1;
    int tuplesize = 0, i;
    cout << "Insert pairs of integers of the form a1 m1 a2 m2...\n";
    cout << "where x = a1 mod m1, x = a2 mod m2, etc.\n";
    cout << "Insert a negative for an a value when finished.\n";
    while (ai >= 0){
	cin >> a[tuplesize];
	ai = a[tuplesize];
	if (ai > 0) cin >> m[tuplesize]; 
	tuplesize ++;
    }
    tuplesize --;	
    x = CRT (a, m, tuplesize);
    for (i=0;i<tuplesize;i++) M *= m[i];
    cout << "x mod "<<M<<" = " << x << "\n";
    
}

// Function CRT
//  Takes an array of residues, an array of moduli, and the number of
//  residue moduli pairs.
//  Functionality: Returns the unique residue mod the product
//   of the moduli via the Chinese Remainder Theorum. If the
//   moduli are not pairwise relativley prime, the function
//   will exit.

Integer CRT(Integer a[], Integer m[], int tuplesize){
    Integer x = 0, yi, Mi;
    Integer M=1, common;
    int i;

    //build M, the product of the moduli.

    for (i=0;i<tuplesize;i++) M *= m[i];
    for (i=0; i<tuplesize; i++){
	Mi = M/m[i];
	ExtendedEuclid (Mi, m[i], &common, &yi);
	if (common != 1) {
	    cout << "Moduli not pairwise relatively prime\n";
	    exit (1);
	}
	//build x via the CRT.
	x += (a[i] * Mi * yi) % M;
    }
    return x % M;
}