C - Programming Guide

C/C++ Program for Implementation of Extended Euclidian Algorithm

#include<iostream.h>
#include<conio.h>

main()
{
  int a,b,x,y,lx,ly,q,temp;
  clrscr();
  cout<<"\n\t\t     *** Extended Euclidian Algorithm ***\n";
  cout<<"\n For : ax + by = gcd(a,b) ";
  cout<<"\n\n Enter value of a :: ";
  cin>>a;
  cout<<"\n Enter value of b :: ";
  cin>>b;

  x=0,lx=1;
  y=1,ly=0;

  while(b!=0)
  {
 q=a/b;
 temp=b;
 b=a%b;
 a=temp;

 temp=x;
 x=lx-(q*x);
 lx=temp;

 temp=y;
 y=ly-(q*y);
 ly=temp;


  }
  cout<<"\n x :: "<<lx<<"\ty :: "<<ly;
  cout<<"\n\n GCD :: "<<a;
  getch();
}

/* Sample Output -


                     *** Extended Euclidian Algorithm ***                       
                                                                                
 For : ax + by = gcd(a,b)                                                       
                                                                                
 Enter value of a :: 5
                                                                                
 Enter value of b :: 8                                                          
                                                                                
 x :: -3        y :: 2                                                          
                                                                                
 GCD :: 1                                                                      


*/