Math · Number theory
Extended Euclidean algorithm calculator.
Enter two integers to get their gcd and whole numbers x and y with a x + b y = gcd(a, b), plus every division step and a check.
Inputs
Result
Enter a and b.
What the extended Euclidean algorithm does
The Euclidean algorithm finds the greatest common divisor by replacing the pair (a, b) with (b, a mod b) until the remainder is 0; the last non-zero remainder is the gcd (Euclid, Elements Book VII). The extended version carries two extra columns so that, at the end, you also have whole numbers x and y satisfying a x + b y = gcd(a, b). These are the Bezout coefficients and they are not unique: adding b / gcd to x and subtracting a / gcd from y gives another valid pair.
Worked example. For 240 and 46: 240 = 5 x 46 + 10, 46 = 4 x 10 + 6, 10 = 1 x 6 + 4, 6 = 1 x 4 + 2, 4 = 2 x 2 + 0. The last non-zero remainder is 2, so gcd = 2, and back-substitution gives 240 x (-9) + 46 x 47 = -2160 + 2162 = 2. The LCM is |a x b| / gcd = 11,040 / 2 = 5,520.
Uses. The same table gives the modular inverse (when gcd = 1) and solves linear Diophantine equations a x + b y = c, which have whole-number solutions exactly when gcd(a, b) divides c.
Frequently asked questions
What is the extended Euclidean algorithm?
It is the Euclidean algorithm for the gcd, carried further to also produce integers x and y with a x + b y = gcd(a, b).
What is gcd(240, 46)?
2. The extended algorithm gives 240 x (-9) + 46 x 47 = 2.
Are the Bezout coefficients unique?
No. If (x, y) works, so does (x + b/g, y - a/g) for any whole-number multiple, where g is the gcd. This tool shows the pair the standard algorithm produces.
How is this used for modular inverses?
If gcd(a, m) = 1 then a x + m y = 1, so a x is 1 mod m and x (reduced mod m) is the inverse of a.
Can I use negative numbers?
Yes. The gcd is always reported as a positive number, and x and y adjust their signs so the identity still holds.
Sources
Checked
The Euclidean algorithm is from Euclid, Elements Book VII (Props 1 and 2). The Bezout identity is checked on every result by multiplying it out. Computed with exact BigInt arithmetic in your browser. Runs entirely in your browser. Nothing you type is sent or stored.
For learning
For learning. Different textbooks may list a different but equally valid pair of Bezout coefficients.