Extended Euclidean Algorithm — Bezout Coefficients

Recursive

long[] extGcd(long a, long b) {
  if (b == 0) return new long[]{a, 1, 0};
  long[] r = extGcd(b, a % b);
  return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
}

Modular inverse

If gcd(a, m) = 1, then a·x ≡ 1 (mod m) where x = extGcd(a, m)[1] mod m.

Chinese Remainder Theorem

ExtGcd is core of CRT construction — combine solutions modulo different coprime moduli.

Applications

RSA key generation. Modular linear equations. Solving Diophantine equations.