Extended Euclidean algorithm code in python

#EXTENDED EUCLIDEAN ALGORITHM TO FIND GCD(M,B)
m=int(raw_input("ENTER M OR mod M = : "))
b=int(raw_input("ENTER B = : "))
# A1,A2,A3 <---(1,0,M)
a1=1
a2=0
a3=m
# B1,B2,B3 <---(0,1,B)
b1=0
b2=1
b3=b
while 1 :
# if B3=0 return A3=GCD(M,B) and B has no inverse 
      if b3==0 :
         gcd_MB=a3
         invrs_b=0
         break
# if B3=1 return B3=GCD(M,B) and B2=B(inverse) mod M
      if b3==1 :
         gcd_MB=b3
         invrs_b=1
         break
# Q=A3/B3 
      q=a3/b3
# (T1,T2,T3) <--- [(A1-QB1),(A2-QB2),(A3-QB3)] 
      t1=a1-q*b1
      t2=a2-q*b2
      t3=a3-q*b3
# (A1,A2,A3) <--- (B1,B2,B3) 
      a1=b1
      a2=b2
      a3=b3
# (B1,B2,B3) <--- (T1,T2,T3) 
      b1=t1
      b2=t2
      b3=t3

if invrs_b==0 :
        print "\nGCD(B,M) = : ",gcd_MB,"\n"
        print "\n", b,"HAS NO MULTIPLICATIVE INVERSE IN mod",m,"\n"

if invrs_b==1 :
#FIND THE MULTIPLICATIVE INVERSE OF B IN mod M by traditional method......
        c=1    
        while ((b*c)%m)!=1 :
                            c=c+1
                            if c>m :
                                    break


#FIND MULTIPLICATIVE INVERSE OF B IN mod M BY value of b2....... 
#c=1
#while c%m!=b2 :
#            c++
#            if (c>m) :
#                  break

        if c<m :
             print  "\nGCD(B,M) = :",gcd_MB
             print  "\nMULTIPLICATIVE INVERSE OF",b, " = " ,c, " in mod",m,"\n"
        else:
             print "\nGCD(B,M) = : ",gcd_MB 
             print "\n",b," HAS NO INVERSE IN mod",m,"\n"

Compile and run in a single command :
system path> python eea.py
It will compile as well as run the program.

Extended Euclidean algorithm code in C

/*EXTENDED EUCLIDEN ALGORITHM FOR FIND GCD OF TWO NUMBERS */
#include < stdio.h >
main(){
int m,b,a1,a2,a3,b1,b2,b3,gcd_MB,invrs_b,q,t1,t2,t3;
char ch='a';
while(ch!='q'){
printf("ENTER M OR mod M= : ");
scanf("%d",&m);
printf("ENTER B = : ");
scanf("%d",&b);
/*A1,A2,A3 <---(1,0,M)*/
a1=1;
a2=0;
a3=m;
/*B1,B2,B3 <---(0,1,B)*/
b1=0;
b2=1;
b3=b;
while(1){
/*if B3=0 return A3=GCD(M,B) and B has no inverse */
if(b3==0){
gcd_MB=a3;
invrs_b=0;
break;
}
/*if B3=1 return B3=GCD(M,B) and B2=B(inverse) mod M*/
if(b3==1){
gcd_MB=b3;
invrs_b=1;
break;
}
/* Q=A3/B3 */
q=a3/b3;
/*(T1,T2,T3) <--- [(A1-QB1),(A2-QB2),(A3-QB3)] */
t1=a1-q*b1;
t2=a2-q*b2;
t3=a3-q*b3;
/*(A1,A2,A3) <--- (B1,B2,B3) */
a1=b1;
a2=b2;
a3=b3;
/*(B1,B2,B3) <--- (T1,T2,T3) */
b1=t1;
b2=t2;
b3=t3;
}
if(invrs_b==0){
printf("\nGCD(B,M) = : %d",gcd_MB);
printf("\n %d HAS NO MULTIPLICATIVE INVERSE IN mod %d \n",b,m);
}
if(invrs_b==1)
{
/*FIND THE MULTIPLICATIVE INVERSE OF B
 IN mod M by traditional method......*/
int c=1;
while(((b*c)%m)!=1)
{
c++;
if(c>m)
break;
}

/*FIND MULTIPLICATIVE INVERSE OF B IN mod M BY value of b2 
int c=1;
while(c%m!=b2){
c++;
if(c>m)
break;
}*/
if(c < m)
{
printf("\nGCD(B,M) = : %d",gcd_MB);
printf("\nMULTIPLICATIVE INVERSE OF %d = %d in mod %d\n",b,c,m);
}
else
{
printf("\nGCD(B,M) = : %d",gcd_MB); 
printf("\n %d HAS NO INVERSE IN mod %d\n",b,m);
}}
scanf("%c",&ch);
}
}

Compile in LINUX environment by:
Compile : gcc -o eea eea.c
Run     :./eea
here gcc is a c/c++ compiler and eea.c is a c sourcecode file.

chinese remainder theorem in c

Chinese_remainder_theorem code in C

#include <stdio.h>
main()
{

int a[10],m[10],M[10],y[10];
int ml=1,n,i,j,x=0;

printf("\nEnter value of a and m as follows : \n");
printf("x mod m1=a1 mod m1\n");
printf("x mod m2=a2 mod m2\n");

printf("what is the value of n less than 10 : ");
printf("\t.\n\t.\n\t.\n\t.\n\t.\n");
printf("x mod mn=an mod mn\n");
scanf("%d",&n);

for(i=1;i<=n;i++)
//enter m1,m2,m3,m4...........mn
printf("\nEnter m1,m2,m3,m4,............,mn\n");
{
printf("m %d : ",i);

for(i=1;i<=n;i++)
scanf("%d",&m[i]);
}
//enter a1,a2,a3,a4,...........an
printf("\nEnter a1,a2,a3,a4,............,an\n");
{

//compute M1,M2,M3,M4...........Mn
printf("a %d : ",i);
scanf("%d",&a[i]);
}
//compute M ?
for(i=1;i<=n;i++)
{
ml=ml*m[i];
}
for(i=1;i<=n;i++)
{

if((y[i]*j)%m[i]==1)
M[i]=ml/m[i];
}
//compute y1,y2,y3,y4...........yn
for(i=1;i<=n;i++)
{
y[i]=M[i]%m[i];
j=1;
while(1)          //find MI
{
break;

printf("\nFinal value of x : %d ans",x);
else j++;
}
y[i]=j;
}
for(i=1;i<=n;i++)
{
x=x+(a[i]*y[i]*M[i])%ml;
}
x=x%ml; //final x is here
printf("\nThank u \n");
return 0;

}

Compiled By :gcc compiler in ubuntu LINUX
copy the code and give name crt.c and follow :

:gcc -o a crt.c    (compile the code).
:./a               (run the program).