Linear Diophantine equation

A linear Diophantine equation in two variables has the form $ax+by=c$ with integer coefficients and seeks integer solutions.

If $a,b$ are nonzero integers, $d=\gcd (a,b)$, and $(x_0,y_0)$ is one solution of the linear Diophantine equation $ax+by=c$, then all solutions areSubtract two solutions and use the fact that $a/d$ and $b/d$ are coprime integers. The linear Diophantine equation solvability criterion says that a particular solution exists exactly when $d$ divides $c$; the extended Euclidean algorithm constructs one. This parametrization separates existence from the complete family of answers.

The equation $ax+by=c$ has an integer solution exactly when $\gcd (a,b)$ divides $c$. Bézout's identity proves sufficiency, while every integer linear combination of $a,b$ is divisible by their greatest common divisor.