Extended GCD & Bezout Calculator

Paste two non-negative integers and the Extended GCD & Bezout Calculator runs the Extended Euclidean Algorithm, producing the GCD, the LCM, and the Bezout coefficients x and y that satisfy a·x + b·y = gcd(a, b). Every step of the Euclidean division chain is shown in a table so you can follow the back-substitution by hand, useful when a contest problem asks you to prove the identity, not just quote the answer.

Competitive programmers reach for this algorithm in two situations: verifying that a modular inverse exists before computing it (the inverse only exists when gcd = 1), and solving linear Diophantine equations ax + by = c, where a solution exists exactly when gcd(a, b) divides c. All arithmetic uses JavaScript BigInt, so inputs up to 10¹⁸ are exact with no floating-point rounding and no silent overflow.

Worked Example: Two Numbers, One Step Trace

Load the sample (252 and 198) and the step trace shows four division rows: 252 = 1·198 + 54, then 198 = 3·54 + 36, then 54 = 1·36 + 18, then 36 = 2·18 + 0. The remainder hits zero at 18, so GCD = 18. Back-substitution yields x = −3, y = 4, verified by 252·(−3) + 198·4 = −756 + 792 = 18. The identity check row confirms this automatically. LCM = 252 × 198 / 18 = 2,772. Because gcd = 18 is not 1, no modular inverse exists for this pair, and the tool reports "An inverse exists only when gcd(a, b) = 1" rather than a silent wrong answer.

What Each Output Field Means

• Bezout x and y are one particular solution to ax + by = gcd. The full solution set is x + k·(b/gcd), y minus k·(a/gcd) for any integer k.
• Modular inverse of a mod b equals x reduced into [0, b), shown only when gcd(a, b) = 1. Plugging it back in gives a·inv ≡ 1 (mod b) exactly.
• LCM(a, b) is computed as (a / gcd) * b to keep intermediate values small. Multiplying a * b first before dividing overflows for inputs near 10¹⁸.
• The Euclidean step count is O(log min(a, b)). For a = 10¹⁸ and b = 10¹⁸ minus 1, the worst case, the trace reaches zero in at most 87 steps.

Edge Cases and When the Tool Cannot Produce a Result

Try a = 6, b = 9. GCD = 3, so no modular inverse exists. The tool shows the exact guard message rather than computing a meaningless result; the bundled C++ snippet returns -1 in this case, which is the convention most competitive-programming templates follow. Entering 0 for both values triggers a separate guard: gcd(0, 0) is undefined, so the algorithm has no meaningful output and the tool says so immediately. The step table is not shown for this input because there are no division steps to trace.