Maths & numbers

Bézout coefficients calculator

Use the extended Euclidean algorithm to find one pair of integer coefficients.

Your numbers

Calculated on your device. Your inputs aren’t sent to us.

Your result

Ready when you are

Enter your inputs and select Calculate.

Report an issue

Behind the numbers

How this calculation works

Adding b/g to x and subtracting a/g from y produces another valid pair, where g is the gcd.

THE FORMULAax + by = gcd(a,b)

A worked example

30 × (−1) + 18 × 2 = 6.

Good to know

Several coefficient pairs can give the same gcd.

Work backward through the Euclidean divisions

For 30 and 18, Euclidean division gives 30 = 18 + 12 and 18 = 12 + 6. The last nonzero remainder is 6. Substitute 12 = 30 − 18 into 6 = 18 − 12 to obtain 6 = 18 − (30 − 18) = −30 + 2 × 18.

The coefficients are therefore x = −1 and y = 2 in 30x + 18y = 6. Multiplying and adding the two terms gives −30 + 36 = 6, which checks the result. The extended Euclidean algorithm tracks the same substitutions while computing the gcd.

Substitution through two Euclidean divisions gives negative thirty plus thirty-six equals six30 = 18 + 1218 = 12 + 66 = −30 + 2 × 18
Back-substitute 12 = 30 − 18 into 6 = 18 − 12. The coefficients of 30 and 18 are −1 and 2.

Understand why the coefficient pair is not unique

If ax + by = d with d = gcd(a,b), adding b/d to x and subtracting a/d from y preserves the sum. For this example, adding 3 to −1 and subtracting 5 from 2 gives x = 2 and y = −3. The check becomes 60 − 54 = 6.

The calculator reports one valid pair rather than listing every pair. For a target c, the equation ax + by = c has an integer solution exactly when d divides c. Multiplying the default coefficients by two therefore gives a solution for target 12. When the gcd is one, the Modular inverse calculator uses one of these coefficients as an inverse modulo the other input.

A few questions, answered

Do the coefficients have to be positive?

No. Negative coefficients are often necessary to make a small gcd from larger positive inputs.

What if I swap the inputs?

A valid identity can be obtained by swapping the coefficient roles as well. The particular pair returned by the algorithm can differ.

Find your calculator

Start typing to explore the library.