// Extended Euclid Algorithm -- iterative version
// uses Knuth's Algorithm E (v. 1 of TAOCP)

// ----------------------------------------------------
//     (c) Copyright 2003  Julian V. Noble.          //
//       Permission is granted by the author to      //
//       use this software for any application pro-  //
//       vided this copyright notice is preserved.   //
// ----------------------------------------------------

// Examples:      99  78 -> 3 -11 14
//              1769 551 -> 29 5 -16

#include <dos.h>        // remove to run under gcc
#include <conio.h>      // remove to run under gcc
#include <stdlib.h>     // remove to run under gcc
#include <stdarg.h>     // remove to run under gcc

#include <math.h>
#include <stdio.h>


xgcd( int m, int n, int *x, int *y);  // prototype

int main(void)
{ 
  clrscr();             // remove to run under gcc
  int a, b, x, y, gcd;

  printf("What are m and n? ");
  scanf(" %d%d", &a, &b);

  gcd = xgcd(a,b,&x,&y);
  printf( " %d %d %d\n", gcd, x, y ) ;
}

  int xgcd( int m, int n, int *x, int *y)
  {
    int xp, yp, q, r, temp;

    *x=0; q=0; xp=1; *y=1; yp=0;

    if (n==0) { *x=1; *y=0; return m; }

    while (n > 0)       //  begin iteration
      {  r = m%n;
         q = m/n;
         temp = xp;
         xp = *x;
         *x = temp - (*x) * q;

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

         m = n;
         n = r;
      }

    *x = xp ;
    *y = yp ;
    return m ;
  }