SG
← Back

Linear Diophantine Equations

ax + by = c has integer solutions iff gcd(a,b) divides c.

mathnumber-theorydiophantineUpdated 2025-09-01

General Solution

  • x = x0 + (b/g)*t
  • y = y0 - (a/g)*t

Find x0,y0

  • From extended Euclid