If are nonzero integers, , and is one solution of the linear Diophantine equation , then all solutions are
Subtract two solutions and use the fact that and are coprime integers. The linear Diophantine equation solvability criterion says that a particular solution exists exactly when divides ; the extended Euclidean algorithm constructs one. This parametrization separates existence from the complete family of answers.
Linear Diophantine equation Created 2026-09-24 Updated 2026-11-05
A linear Diophantine equation in two variables is with integer coefficients and unknown integers . Assume are not both zero, and put .
The linear Diophantine equation solvability criterion gives a solution exactly when : every integer linear combination is divisible by , and Bézout's identity supplies a combination equal to which can be multiplied by . The extended Euclidean algorithm constructs the coefficients. All solutions of a linear Diophantine equation then describes the complete one-parameter family when both coefficients are nonzero.
For example, has , and all its solutions are , with . There is no solution with both coordinates nonnegative, since those inequalities require and . Thus an integer-solvability test does not automatically settle a problem requiring nonnegative integers. If both coefficients are zero, the separate equation has every integer pair as a solution when , and none otherwise.
Applying the Euclidean algorithm,
Hence . Since does not divide , the linear Diophantine equation solvability criterion gives
The linear Diophantine equation solvability criterion says that has an integer solution exactly when divides . The Euclidean algorithm gives
Thus , which divides . Therefore