// C++ program to combine modular equations // using Chinese Remainder Theorem #include   using namespace std; // function that implements Extended euclidean // algorithm vector<int> extended_euclidean(int aint b){  if(a == 0){  vector<int> temp;  temp.push_back(b);  temp.push_back(0);  temp.push_back(1);   return temp;  }  else{  vector<int> temp(3);  temp= extended_euclidean(b % a a);  int g = temp[0];  int y = temp[1];  int x = temp[2];  temp[0] = g;  temp[1] = x - ((b/a) * y);  temp[2] = y;  return temp;  }  vector<int> temp;  return temp; } // modular inverse driver function int modinv(int aint m){  vector<int> temp(3);  temp = extended_euclidean(a m);  int g = temp[0];  int x = temp[1];  int y = temp[2];    // Since we are taking the modulo of   // negative numbers so to have positive   // output of the modulo we use this formula.   int ans = x - (floor(x/(float)m) * m);  return ans; }   // function implementing Chinese remainder theorem // list m contains all the modulii // list x contains the remainders of the equations int crt(vector<int> &mvector<int> & x) {    // We run this loop while the list of  // remainders has length greater than 1  while(1)  {    // temp1 will contain the new value   // of A. which is calculated according   // to the equation m1' * m1 * x0 + m0'  // * m0 * x1  int var1 = (modinv(m[1]m[0]));  int var2 = (modinv(m[0]m[1]) );  // cout << var1 << ' ' << var2 << endl;  int temp1 = (modinv(m[1]m[0])) * x[0] * m[1] + (modinv(m[0]m[1]) )* x[1] * m[0];  // temp2 contains the value of the modulus  // in the new equation which will be the   // product of the modulii of the two  // equations that we are combining  int temp2 = m[0] * m[1];  // cout << temp1<< ' '<  // we then remove the first two elements  // from the list of remainders and replace  // it with the remainder value which will  // be temp1 % temp2  x.erase(x.begin());  x.erase(x.begin());  x.insert(x.begin() temp1%temp2);  //we then remove the first two values from  //the list of modulii as we no longer require  // them and simply replace them with the new   // modulii that we calculated  m.erase(m.begin());  m.erase(m.begin());  m.insert(m.begin() temp2);  // once the list has only one element left  // we can break as it will only contain   // the value of our final remainder  if(x.size()== 1){  break;  }  }    // returns the remainder of the final equation  return x[0]; } // driver segment int main(){  vector<int> m = {4 7 9 11};  vector<int> x = {3 4 1 0};  cout << crt(m x) << endl;  return 0; } // The code is contributed by Gautam goel (gautamgoe962) 

// Java program to implement the Chinese Remainder Theorem import java.util.ArrayList; import java.math.BigInteger; public class ChineseRemainderTheorem {  // Function to calculate the modular inverse of a and m  public static BigInteger modinv(BigInteger a BigInteger m) {  BigInteger m0 = m;  BigInteger y = BigInteger.ZERO;  BigInteger x = BigInteger.ONE;  if (m.equals(BigInteger.ONE))  return BigInteger.ZERO;  while (a.compareTo(BigInteger.ONE) == 1) {  BigInteger q = a.divide(m);  BigInteger t = m;  m = a.mod(m);  a = t;  t = y;  y = x.subtract(q.multiply(y));  x = t;  }  if (x.compareTo(BigInteger.ZERO) == -1)  x = x.add(m0);  return x;  }  // Function to implement the Chinese Remainder Theorem  public static BigInteger crt(ArrayList<BigInteger> m ArrayList<BigInteger> x) {  BigInteger M = BigInteger.ONE;  for (int i = 0; i < m.size(); i++) {  M = M.multiply(m.get(i));  }  BigInteger result = BigInteger.ZERO;  for (int i = 0; i < m.size(); i++) {  BigInteger Mi = M.divide(m.get(i));  BigInteger MiInv = modinv(Mi m.get(i));  result = result.add(x.get(i).multiply(Mi).multiply(MiInv));  }  return result.mod(M);  }  public static void main(String[] args) {  ArrayList<BigInteger> m = new ArrayList<>();  ArrayList<BigInteger> x = new ArrayList<>();  m.add(BigInteger.valueOf(4));  m.add(BigInteger.valueOf(7));  m.add(BigInteger.valueOf(9));  m.add(BigInteger.valueOf(11));  x.add(BigInteger.valueOf(3));  x.add(BigInteger.valueOf(4));  x.add(BigInteger.valueOf(1));  x.add(BigInteger.valueOf(0));  System.out.println(crt(m x));  } } // This code is contributed by Vikram_Shirsat 

# Python 2.x program to combine modular equations # using Chinese Remainder Theorem # function that implements Extended euclidean # algorithm def extended_euclidean(a b): if a == 0: return (b 0 1) else: g y x = extended_euclidean(b % a a) return (g x - (b // a) * y y) # modular inverse driver function def modinv(a m): g x y = extended_euclidean(a m) return x % m # function implementing Chinese remainder theorem # list m contains all the modulii # list x contains the remainders of the equations def crt(m x): # We run this loop while the list of # remainders has length greater than 1 while True: # temp1 will contain the new value  # of A. which is calculated according  # to the equation m1' * m1 * x0 + m0' # * m0 * x1 temp1 = modinv(m[1]m[0]) * x[0] * m[1] +  modinv(m[0]m[1]) * x[1] * m[0] # temp2 contains the value of the modulus # in the new equation which will be the  # product of the modulii of the two # equations that we are combining temp2 = m[0] * m[1] # we then remove the first two elements # from the list of remainders and replace # it with the remainder value which will # be temp1 % temp2 x.remove(x[0]) x.remove(x[0]) x = [temp1 % temp2] + x # we then remove the first two values from # the list of modulii as we no longer require # them and simply replace them with the new  # modulii that we calculated m.remove(m[0]) m.remove(m[0]) m = [temp2] + m # once the list has only one element left # we can break as it will only contain  # the value of our final remainder if len(x) == 1: break # returns the remainder of the final equation return x[0] # driver segment m = [4 7 9 11] x = [3 4 1 0] print crt(m x) 

using System; using System.Collections; using System.Collections.Generic; using System.Linq; // C# program to combine modular equations // using Chinese Remainder Theorem class HelloWorld {  // function that implements Extended euclidean  // algorithm  public static List<int> extended_euclidean(int aint b){  if(a == 0){  List<int> temp = new List<int>();  temp.Add(b);  temp.Add(0);  temp.Add(1);   return temp;  }  else{  List<int> temp = new List<int>();  temp.Add(0);  temp.Add(0);  temp.Add(0);  temp= extended_euclidean(b % a a);  int g = temp[0];  int y = temp[1];  int x = temp[2];  temp[0] = g;  temp[1] = x - ((b/a) * y);  temp[2] = y;  return temp;  }  List<int> temp1 = new List<int>();  return temp1;  }  // modular inverse driver function  public static double modinv(int aint m){  List<int> temp = new List<int>();  temp.Add(0);  temp.Add(0);  temp.Add(0);  temp = extended_euclidean(a m);  int g = temp[0];  int x = temp[1];  int y = temp[2];  // Since we are taking the modulo of   // negative numbers so to have positive   // output of the modulo we use this formula.   double val = Math.Floor(((double)x/(double)m));  double ans = x - (val * m);  return ans;  }  // function implementing Chinese remainder theorem  // list m contains all the modulii  // list x contains the remainders of the equations  public static int crt(List<int> mList<int> x)  {  // We run this loop while the list of  // remainders has length greater than 1  while(true)  {  // temp1 will contain the new value   // of A. which is calculated according   // to the equation m1' * m1 * x0 + m0'  // * m0 * x1  double var1 = (modinv(m[1]m[0]));  double var2 = (modinv(m[0]m[1]));  // cout << var1 << ' ' << var2 << endl;  double temp1 = (modinv(m[1]m[0])) * x[0] * m[1] + (modinv(m[0]m[1]) )* x[1] * m[0];  // temp2 contains the value of the modulus  // in the new equation which will be the   // product of the modulii of the two  // equations that we are combining  int temp2 = m[0] * m[1];  // cout << temp1<< ' '<  // we then remove the first two elements  // from the list of remainders and replace  // it with the remainder value which will  // be temp1 % temp2  x.RemoveAt(0);  x.RemoveAt(0);  x.Insert(0 (int)temp1%(int)temp2);  //we then remove the first two values from  //the list of modulii as we no longer require  // them and simply replace them with the new   // modulii that we calculated  m.RemoveAt(0);  m.RemoveAt(0);  m.Insert(0 temp2);  // once the list has only one element left  // we can break as it will only contain   // the value of our final remainder  if(x.Count == 1){  break;  }  }  // returns the remainder of the final equation  return x[0];  }  static void Main() {  List<int> m = new List<int>(){  4 7 9 11  };  List<int> x = new List<int> (){  3 4 1 0  };  Console.WriteLine(crt(m x));  } } // The code is contributed by Nidhi goel.  

// JavaScript program to combine modular equations // using Chinese Remainder Theorem // function that implements Extended euclidean // algorithm function extended_euclidean(a b){  if(a == 0){  let temp = [b 0 1];  return temp;  }  else{  let temp= extended_euclidean(b % a a);  let g = temp[0];  let y = temp[1];  let x = temp[2];  temp[0] = g;  temp[1] = x - (Math.floor(b/a) * y);  temp[2] = y;  return temp;  }  let temp;  return temp; } // modular inverse driver function function modinv(a m){  let temp = extended_euclidean(a m);  let g = temp[0];  let x = temp[1];  let y = temp[2];    // Since we are taking the modulo of   // negative numbers so to have positive   // output of the modulo we use this formula.   let ans = x - (Math.floor(x/m) * m);  return ans; }   // function implementing Chinese remainder theorem // list m contains all the modulii // list x contains the remainders of the equations function crt(m x) {    // We run this loop while the list of  // remainders has length greater than 1  while(1)  {    // temp1 will contain the new value   // of A. which is calculated according   // to the equation m1' * m1 * x0 + m0'  // * m0 * x1  let var1 = (modinv(m[1]m[0]));  let var2 = (modinv(m[0]m[1]) );  // cout << var1 << ' ' << var2 << endl;  let temp1 = (modinv(m[1]m[0])) * x[0] * m[1] + (modinv(m[0]m[1]) )* x[1] * m[0];  // temp2 contains the value of the modulus  // in the new equation which will be the   // product of the modulii of the two  // equations that we are combining  let temp2 = m[0] * m[1];  // cout << temp1<< ' '<  // we then remove the first two elements  // from the list of remainders and replace  // it with the remainder value which will  // be temp1 % temp2  x.shift();  x.shift();  x.unshift(temp1 % temp2);  //we then remove the first two values from  //the list of modulii as we no longer require  // them and simply replace them with the new   // modulii that we calculated  m.shift();  m.shift();  m.unshift(temp2);  // once the list has only one element left  // we can break as it will only contain   // the value of our final remainder  if(x.length== 1){  break;  }  }    // returns the remainder of the final equation  return x[0]; } // driver segment let m = [4 7 9 11]; let x = [3 4 1 0]; console.log(crt(m x)); // The code is contributed by phasing17