extended euclidean algorithm

extended-gcd.cpp

#include <stdio.h>   

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

       int x1, y1;
       
       int gcd = egcd(b%a, a, &x1, &y1);
      

       *x = y1 - (b / a) * x1;
      
       *y = x1;

       return gcd;
}

int main() {
       int x, y;
       int a = 35, b = 15;
       int g = egcd(a, b, &x, &y);
       printf("gcd  = %d, x = %d, y = %d\n", g, x, y);
}