Program to find the numbers co prime to each other.

#include

#include



int exteuclid(int a,int b);



void main()

{

   int a[20],M=1,x[20],i,b[20],c[20],A[20],e,T,j,p=0;

     // M[0]=1;

   clrscr();

   printf("Enter the no of m's which must be co prime to each other\n");

   scanf("%d",&e);

   printf("Enter the values of m's\n");

   for(i=0;i   scanf("%d",&a[i]);        //taking input small m's....



     printf("Enter the values of A's\n");

     for(i=0;i      scanf("%d",&A[i]);     //taking input A's......







    for(i=0;i    {

    M=M*a[i];           //calculating M....

    }

     printf("M=%d\n",M);

    // T=M[i];

   for(i=0;i   {

     b[i]=M/a[i];        //calculating M1,M2,M3.....and so on..



   }

   for(i=0;i     printf("M%d=%d\t",i+1,b[i]);





	      for(i=0;i	       {

		 c[i]=exteuclid(a[i],b[i]); //calculating multiplicative inverse....



	       }

		for(i=0;i		 printf("MI%d=%d\t",i+1,c[i]);



		for(i=0;i		{

		x[i]=A[i]*b[i]*c[i];

		}

		for(i=0;i		{

		p=p+x[i];



		}

		p=p%M;







		printf("our unique value x=%d",p);













   getch();

}





      int exteuclid(int a,int b)

      {

      int A2, A1, B2, B1, A3, B3,T1,T2,T3,q, r = 1, t, x;



     A1 = B2 = 1;

     A2 = B1 = 0;

     A3 = a;

     B3= b;





     do

	  {

	  q = (A3/B3);

	  r = (A3% B3);

	  //printf("%d\t %d\t %d\t %d\t %d\t %d\t %d\t %d\n",

		  //  A1, A2, B1, B2, c, d, q, r);



	       T1=A1-q*B1;

	       T2=A2-q*B2;

	       T3=A3-q*B3;

	       A1=B1;

	       A2=B2;

	       A3=B3;

	       B1=T1;

	       B2=T2;

	       B3=T3;



	  } while(r !=1);

	  return(B2);

    }

Related Links :