// -------------------------------------------------------------------------- 

// Extended Euclid Algorithm -- recursive version
// (with thanks to M. Hendrix for elucidation of indirection)

// ----------------------------------------------------
//     (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 a, int b, int *c, int *d); // prototype

int main(void)
{ 
  int a, b, c, d, gcd;

  clrscr();             // remove to run under gcc

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

  gcd = xgcd(a,b,&c,&d);
  printf( " %d %d %d\n", gcd, c, d) ;
  return 0;
}

  int xgcd( int a, int b, int *x, int *y)   // recursive
  {
    int gcd, temp;

    if(b==0)
    { *x=1;
      *y=0;
      return a;
    }

    gcd = xgcd(b,a%b,x,y);

    temp = *y;          // compute x and y recursively
    *y = *x - (*y) * (a/b);
    *x = temp;

    return gcd;
  }
// --------------------------------------------------------------------------