Расширенный алгоритм Евклида и вычисление обратного элемента по модулю в кольце

Написана функция, вычисляющая НОД целых чисел a и b и находящая целые коэффициенты x и y, такие, что ax + by = НОД(a, b). На основе этой функции написана новая функция, вычисляющая обратный элемент к a в кольце вычетов по модулю n, или сообщающая, что такого элемента не существует.

int gcdex(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int d1 = gcdex(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return d1;
}

// Function returns 1 if such element doesn't exist and 0 if exists and puts it
// in result.
int ReverseElement(int a, int N, int &result) {
  int x, y, d;
  d = gcdex(a, N, x, y);
  if (d != 1) {
    return 1;
  } else {
    result = x;
    return 0;
  }
}