THÉORÈME CHINOIS

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define val 100
long pgdc (long a,long b);
long inverse (long a1, long b1);

	      /*-----program principal------*/
int main()
{ void entete();      //declaration de la fction entete
  int tab_a[val],tab_n[val],tab_q[val],tab_qq[val];
  int nbr_eq,i,j,k;
  long n=1,solution=0;
  clrscr();
  entete();           //appel de la fction entete
  do{
  printf("donnez le nombre d'equations qu'il ya dans votre systeme  "); scanf("%d",&nbr_eq);
  }while(nbr_eq<1 || nbr_eq>val);

       /*------------saisie des ai et ni--------------*/
   for(i=0;i<nbr_eq;i++)
     {
       printf("saisissez l'element a%d de l'equation%d  ",i+1,i+1);
       scanf("%d",&tab_a[i]);
      }
      printf("\n\tsaisie des modules parielles\n");

    for(i=0;i<nbr_eq;i++)
     {
       printf("saisissez l'element n%d de l'equation%d  ",i+1,i+1);
       scanf("%d",&tab_n[i]);
     }
      
             /*--------------test si les ni sont  premiers deux a deux------*/
    for(i=0;i<nbr_eq-1;i++)
      {
	for(j=i+1;j<nbr_eq;j++)
	  { if(pgdc(tab_n[i],tab_n[j])!=1)
	     { cprintf("les elements %d et %d ne sont pas premiers ntre eux",tab_n[i],tab_n[j]);
	       printf("\nreprenez la saisie des ni\n");
	       for(k=0;k<nbr_eq;k++)
		{
		printf("saisissez l'element n%d de l'equation%d  ",k+1,k+1);
		scanf("%d",&tab_n[k]);
		}
	     }
	   }
      }

      clrscr();entete();textbackground(BLACK);
	       
             /*------------affichage du systeme--------------*/
     printf("\nle systeme saisi est");
     for(i=0;i<nbr_eq;i++)
       {textcolor(CYAN);printf("\n");
	cprintf("  x=%d mod %d",tab_a[i],tab_n[i]);

	}
	     
               /*-----------calcul du produit des ni-----------*/
      for(i=0;i<nbr_eq;i++)
	 n*=tab_n[i];
	 printf("\nle n est %d",n);
		       //calcul et affichage des qi et qqi
      printf("\nles qi sont:  ");
      for(i=0;i<nbr_eq;i++)
	 {
	   tab_q[i]=n/tab_n[i];
	   printf("q%d=%d\t",i+1,tab_q[i]);
	  }
      printf("\nles inverses respectives des qi dans Zi sont:  ");
      for(i=0;i<nbr_eq;i++)
	 {
	   tab_qq[i]=inverse(tab_q[i],tab_n[i]);
	   printf("q'%d=%d\t",i+1,tab_qq[i]);
	  }
		 /*--------calcul solution finale-------------*/
       for(i=0;i<nbr_eq;i++)
	  solution+=((tab_a[i])*(tab_q[i])*(tab_qq[i]));
	  solution%=n;
       printf("\n\n"); textcolor(RED);textbackground(YELLOW);
       cprintf("la solution de cette equation est %d",solution);
       gotoxy(1,49);textcolor(CYAN);cprintf("taper une touche pour sortir...");
       getch();
       return 0;
 }

    /*------------definition de la fction inverse--------*/

  long inverse (long a, long b)
{
 long Ro=a,R1=b,q,r,i=0,Vo=0,V1=1,Uo=1,U1=0,V2,U2;
 long vect_u[50];

do
{
q=Ro/R1;     r=Ro-R1*q;     Ro=R1;        R1=r;
i++;
U2=Uo-q*U1;       V2=Vo-q*V1;
Uo=U1;            U1=U2;
Vo=V1;            V1=V2;
vect_u[i]=U2;
}
while(r!=0);

 if(vect_u[i-1]>0)      return vect_u[i-1]%b;
 else                   return b-(-vect_u[i-1])%b;
}

	  /*-----------definition de la fction pgdc--------------*/

long pgdc (long a,long b)
{long r0,r1,q1,i;
 if (a==0 )         return b;
 if (b==0 )         return a;
 if (a>b)
  {r0=a;  r1=b;}
  else {r0=b; r1=a;}
 q1=r0/r1;
 i=r0-q1*r1;
 if (i==0)
  return r1;
  else
   {
     do
     {
      r0=r1;
      r1=i;
      q1=r0/r1;
      i=r0-q1*r1;
      }while (i!=0);
     return r1;
   }
 }
		   /*-----------definition de l'entete-----------*/
 void entete ()
 { int a,b;
   textcolor(RED);
   gotoxy(10,2);cprintf("++-------------------------------------------------------------++");
   gotoxy(10,3);cprintf("|+-------------------------------------------------------------+|"); a=wherex(); b=wherey();
   gotoxy(10,4);cprintf("||");  gotoxy(10,5);cprintf("||"); gotoxy(a-2,b+2);cprintf("||");gotoxy(a-2,b+1);cprintf("||");
   gotoxy(10,6);cprintf("|+-------------------------------------------------------------+|");
   gotoxy(10,7);cprintf("+--------------------------------------------------------------++");
   textbackground(WHITE);
   textcolor(BLUE);gotoxy(15,4);
   cprintf("CE PROGRAMME RESOUD UN SYSTEME DE CONGRUENCE D'ORDRE N"); gotoxy(23,5);
   cprintf(" A L'AIDE DU THEOREME CHINOIS"); gotoxy(2,9);
 }