bezout identity calculator

What is Bézout's Identity?

Bézout's Identity is a core theorem in number theory. It states that for any integers a and b (not both zero), there exist integers x and y such that:

ax + by = gcd(a,b)

This is powerful because it connects linear combinations with the greatest common divisor (GCD). The coefficients x and y are often called Bézout coefficients, and they can be found efficiently using the Extended Euclidean Algorithm.

How this Bézout Identity Calculator Works

• It validates your inputs as integers.
• It computes gcd(a,b) with the Euclidean algorithm.
• It computes one valid pair of Bézout coefficients (x, y).
• It verifies the identity by substituting values back into ax + by.
• If you provide a target c, it checks whether ax + by = c has an integer solution.

Why This Matters in Real Problems

1) Solving Linear Diophantine Equations

Equations of the form ax + by = c have integer solutions if and only if gcd(a,b) divides c. Once you have one solution, infinitely many solutions can be generated.

2) Modular Inverse and Cryptography

In modular arithmetic, an inverse of a mod n exists when gcd(a,n)=1. The Bézout coefficient of a directly gives the inverse. This is heavily used in cryptographic systems like RSA.

3) Number Theory and Algorithm Design

Extended GCD appears in competitive programming, symbolic math, and algebra systems. It is fast, reliable, and fundamental.

Example

Suppose a = 240 and b = 46. The calculator finds:

• gcd(240,46) = 2
• One coefficient pair is x = -9, y = 47
• Check: 240(-9) + 46(47) = -2160 + 2162 = 2

If you want 240x + 46y = 10, this is solvable because 2 | 10. A specific solution can be generated by scaling the coefficients by 10/2 = 5.

Edge Cases to Know

• Negative values are allowed and handled correctly.
• If one number is zero, the gcd is the absolute value of the other number.
• If both are zero, gcd(0,0)=0 and the equation becomes degenerate.
• Very large integers beyond JavaScript's safe integer range are not supported exactly.

Frequently Asked Questions

Are Bézout coefficients unique?

No. There are infinitely many coefficient pairs. The calculator returns one valid pair.

How do I get all solutions to ax + by = c?

If one solution is (x0,y0) and g = gcd(a,b), then all integer solutions are:

x = x0 + (b/g)t and y = y0 - (a/g)t, for any integer t.

Can I use this for modular inverses?

Yes. Set b = n and inspect the coefficient of a. If gcd(a,n)=1, that coefficient (mod n) is the modular inverse.