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.
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.
The equation has an integer solution exactly when divides . Bézout's identity proves sufficiency, while every integer linear combination of is divisible by their greatest common divisor.

Articles by others on the same topic (0)

There are currently no matching articles.