§ Modular inverse calculation

pair<int, int> euc(int x, int y) {
  if (x < y) { return euc(y, x); }
  // x > y
  if (x % y == 0) { return {0, 1}; }
  int a, b; std::tie(a, b) = euc(y, x%y);
  // ay + b(x%y) = gcd(y, x%y) = gcd(x, y)
  // ay + b(x - y(x//y)) = gcd(y, x%y) = gcd(x, y)
  // ay + bx - by(x//y)  = gcd(y, x%y) = gcd(x, y)
  // (a - b(x//y))y + bx = gcd(y, x%y) = gcd(x, y)
  // bx + (a - b(x//y))y = gcd(y, x%y) = gcd(x, y)
  // intuition?
  return {b, a - b*(x/y)};
}