Linear Diophantine Equations

Existence + one solution

long[] solve(long a, long b, long c) {
  long[] r = extGcd(a, b);
  long g = r[0];
  if (c % g != 0) return null;
  long factor = c / g;
  return new long[]{r[1] * factor, r[2] * factor};
}

All solutions

Given (x0, y0), general solution: x = x0 + k·(b/g), y = y0 - k·(a/g) for integer k.

Constrained

Find x, y in [0, M]: solve for k such that both coordinates in range. Interval arithmetic.

Applications

Coin change with 2 denominations. Chicken-egg problem. RSA key generation.