= All solutions of a linear Diophantine equation
{title2=$(x,y)=(x_0,y_0)+t(b/d,-a/d)$}
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 are
$$
x=x_0+\frac bd\,t,\qquad y=y_0-\frac ad\,t,\qquad t\in\mathbb Z.
$$
Subtract 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.
Back to article page
