Euclid Extended

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

  int gcd = gcd_extend(b % a, a, x, y);
  int temp = *x;
  *x = *y - (b/a)*(*x);
  *y = temp;
  
  return gcd;
}