HesapHanem

Bezout Coefficients Calculator

Enter integers a and b to get the GCD and Bezout coefficients x and y.

How it is calculated

The tool runs the extended Euclidean algorithm on two integers a and b. It repeats a = q·b + r, replacing (a, b) by (b, r) until the remainder is 0, while updating a pair of coefficients at each step so that the current remainder is always a combination of the original a and b. The last non-zero remainder is the GCD, and the tracked coefficients are x and y with a·x + b·y = gcd(a, b). Both inputs must be whole numbers; a decimal such as 4.5 returns no result, and a = b = 0 is not allowed. Negative integers work, and the GCD is always reported as positive. The pair (x, y) is one valid solution; infinitely many others exist.

Worked example

Take a = 240 and b = 46. Divisions: 240 = 5·46 + 10, 46 = 4·10 + 6, 10 = 1·6 + 4, 6 = 1·4 + 2, 4 = 2·2 + 0. The last non-zero remainder is 2, so the GCD is 2. Substituting back through the steps gives x = -9 and y = 47. Check: 240 × (−9) + 46 × 47 = −2160 + 2162 = 2, which matches the GCD.

Try this example →

Common mistakes

  • Entering decimals or fractions; the identity works for integers only, so 4.5 and 6 give nothing.
  • Expecting a unique answer: other pairs such as (x + 46, y − 240) also satisfy the equation, and the tool returns just one.
  • Using the result to find a modular inverse when the GCD is not 1; an inverse of a modulo b exists only if gcd(a, b) = 1.
  • Forgetting that a negative x is normal; to get the inverse of a mod b, add b to a negative x.
  • Reading y as the coefficient of a; x multiplies a and y multiplies b.

Sources

About this calculator

Bezout's identity states that for any integers a and b, there exist integers x and y — the Bezout coefficients — satisfying ax + by = gcd(a, b). This calculator finds x, y and the GCD using the extended Euclidean algorithm, which runs the ordinary GCD algorithm forward while tracking the coefficients backward through each remainder step.

Beyond number theory, Bezout coefficients are the standard way to compute a modular multiplicative inverse — essential in RSA and other cryptographic key generation — and they underlie solving linear Diophantine equations of the form ax + by = c.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    The coefficients also solve equations of the form ax + by = c, as long as c is a multiple of the GCD. For 240 and 46 the GCD is 2, so c = 10 works: scale x = -9 and y = 47 by 5 to get x = -45 and y = 235, and check that 240 times -45 plus 46 times 235 equals 10. If c is not a multiple, no integer solution exists. What kind of equation are you solving?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators