Teorema Chino del Resto

Supongamos que

son enteros coprimos dos a dos. Entonces, para enteros dados

existe un entero x que resuelve el sistema de congruencias simultáneas


Codigo en C++

El siguiente algoritmo necesita las siguientes funciones :

Inverso_Zn() (Inverso en Zn, puedes ver el código aqui)

void chino_del_resto()
{
 int num_ec;
 cout<<"                forma de ecuacion : x = a (mod m)\n\n"; 
 cout<<" ingrese el numero de ecuaciones : ";
 cin>>num_ec;  
 cout<<endl;
 int a[num_ec],m[num_ec],M[num_ec],y[num_ec],x=0;
 
 for(int i=0;i<num_ec;i++)
 {
   cout<<"  a"<<i+1<<" : ";
   cin>>a[i];
 }
 cout<<endl<<endl;
 for(int i=0;i<num_ec;i++)
 {
   cout<<"  m"<<i+1<<" : ";
   cin>>m[i];
 }

  int prod=1;
  // calculamos el producto
  for(int i=0;i<num_ec;i++)
  {
    prod*=m[i];
  }
  for(int i=0;i<num_ec;i++)
  {
  M[i]=prod/m[i];
  }
  for(int i=0;i<num_ec;i++)
  {
   y[i]=Inverso_Zn(M[i]mm[i]);      
  }

  for(int i=0;i<num_ec;i++)
  {
    x+=a[i]*M[i]*y[i];
  }
  x%=prod;
  cout<<"\n  el valor de x es : "<<x<<endl;

}


int main(int argc, char *argv[])
{
    int op;
    cout<<"\n\n         TEOREMA CHINO DEL RESTO\n\n";      
    chino_del_resto();      

    cout<<endl;    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}