Bézout coefficients calculator

Bézout's identity states that for any integers a and b that are not both zero, there exist integers x and y such that a times x plus b times y equals the greatest common divisor of a and b. Those coefficients are the constructive heart of linear Diophantine equations, modular inverses when the gcd is one, and classroom proofs that two numbers are coprime.

What Bézout's identity asserts and why coefficients matter

Every pair of integers that is not both zero has a well-defined non-negative greatest common divisor g. Bézout's identity goes further: it guarantees integers x and y for which a times x plus b times y equals that g. The existence proof is constructive and follows from the Euclidean remainder process.

Ordinary division repeatedly replaces a pair with the next remainder until zero appears; the last non-zero remainder is the gcd. Tracking how each remainder is written as an integer linear combination of the original inputs yields the coefficients at termination. Classroom texts often back-substitute quotients from the division table; production code usually updates two coefficient pairs in a single loop so no stack of remainders is stored.

Both approaches compute the same mathematical object. The coefficients are not unique: if one pair works, so does every pair shifted by integer multiples of b over g and a over g with opposite signs. This tool returns one particular solution from the iterative algorithm, always with a non-negative gcd, so scripts and graders can compare against a fixed convention without re-deriving the general solution set.

How to call the calculator and read the response

Send integers a and b. The pair zero and zero is also rejected, because gcd of zero and zero is undefined and no coefficients can make a meaningful Bézout equation. On success the response includes the normalized a and b, the gcd, x, y, a nested bezout object with the same coefficients, a numeric check equal to a times x plus b times y, an equation string such as two hundred forty times negative nine plus forty-six times forty-seven equals two, and an identity field stating the general relation.

Typical checks: for two hundred forty and forty-six the gcd is two with one valid solution x equals negative nine and y equals forty-seven; for a prime pair with gcd one the coefficients give a modular inverse of a modulo b after reducing x. Edge cases with a zero and a non-zero partner yield gcd equal to the absolute value of the non-zero input and a trivial coefficient pattern.

Where Bézout coefficients appear in practice

Contest programmers solve a times x plus b times y equals c by first computing the gcd and a base Bézout pair, then scaling and parametrizing the general solution when the gcd divides c. Cryptography students recover modular inverses for RSA toy examples and affine ciphers whenever the gcd of a and m equals one by reading the coefficient of a after reduction modulo m. Teachers assign constructive proofs that two integers are coprime and need a deterministic oracle that shows the linear combination, not only a true-or-false coprimality bit.

Data and systems engineers occasionally need explicit linear combinations when reconciling periodic schedules or stride arithmetic. Use the browser tool to check homework quickly, then automate the identical contract when your service needs bulk Diophantine checks. If you only need the plain gcd without coefficients, this landing still answers that need while teaching the stronger constructive Bézout result that underpins number-theory curricula and interview questions about extended Euclidean reasoning.