Bézout identities and integer equations

Every remainder in Euclid is an integer combination of the original inputs. Initially this is obvious for a and b. If two successive quantities are combinations, subtracting an integer multiple of one from the other produces another combination. At termination the gcd d therefore has the form au + bv. The coefficients u and v are not generally positive or unique; allowing subtraction is precisely what makes the statement true.

Back substitution recovers the coefficients explicitly. Solve the last nonzero remainder equation for d, replace the preceding remainder by its expression, and repeat until only a and b remain. Keep parentheses until coefficients are collected, since a sign error is easy to hide in mental substitution. Once found, check the identity by direct multiplication. This supplies both a numerical answer and a proof that no larger common divisor was overlooked.

Suppose ax + by = c. Every common divisor of a and b must divide the left side and hence c. In particular d must divide c; if it does not, stop immediately. Conversely, if c = dt, multiply the Bézout identity by t to obtain one solution x = tu and y = tv. Necessity and sufficiency are different arguments, and together they establish a complete decision rule.

To find every solution, subtract a known solution from an arbitrary one. Write a = da′ and b = db′ with coprime a′ and b′. The difference equation becomes a′Δx = −b′Δy. A Bézout identity for a′ and b′, multiplied by Δx, shows that b′ divides Δx: both resulting terms are multiples of b′. Thus Δx = b′k and Δy = −a′k. This argument assumes both coefficients are nonzero; if one is zero, solve the remaining one-variable equation and leave the unused variable arbitrary.

The parameter describes a lattice of points along a real straight line. Adjacent integer solutions differ by a fixed direction vector, so the real line is continuous while the allowed integer points are discrete. Additional constraints such as nonnegative coin counts restrict k to an interval of integers. Bézout guarantees an integer solution when d divides c, but it does not guarantee that this interval contains an integer.

This distinction matters in scheduling, inventory, and modular inverses. An equation may be solvable with negative x, which corresponds to subtraction in arithmetic but may have no direct interpretation as a purchase count. Translate each practical restriction into an inequality on k after deriving the complete family. Testing a few positive guesses cannot establish impossibility, whereas an empty parameter interval gives a short proof. Retaining every solution first makes the later feasibility check systematic.