Calculators
Extended Euclidean Algorithm Calculator
Find exact GCD and Bézout coefficients for two signed integers, with a verification equation and all integer solutions.
Enter two signed integers, each up to 100 digits, with at least one nonzero. Find GCD and coefficients x and y such that ax + by = GCD(a, b). Calculations stay in your browser.
How the extended Euclidean algorithm works
The extended Euclidean algorithm finds the greatest common divisor g and integers x and y satisfying ax + by = g (Bézout’s identity). It tracks coefficients while repeatedly dividing with remainder. For a = 240 and b = 46, g = 2, x = −9 and y = 47: 240 × (−9) + 46 × 47 = 2. Coefficients are not unique. Every solution is x = x₀ + (b/g)t and y = y₀ − (a/g)t for an integer t. Negative inputs and a single zero are supported; both zero is rejected. Enter up to 100 digits per integer with an optional minus sign. Surrounding whitespace and leading zeros are accepted; plus signs, decimals, separators and scientific notation are rejected. Exact BigInt arithmetic runs in your browser without uploading or storing inputs.
Frequently Asked Questions
Everything you need to know about this tool, how it works, and privacy.
What does the extended Euclidean algorithm calculate?
It finds the non-negative GCD g and integer coefficients x and y satisfying ax + by = g.
Are Bézout coefficients unique?
No. From one pair x₀ and y₀, every pair is x = x₀ + (b/g)t and y = y₀ − (a/g)t for any integer t.
Can I enter negative numbers or zero?
Yes. Either integer may be negative or zero, but both cannot be zero. Each input accepts up to 100 digits with an optional minus sign.
How is this related to modular inverses?
If gcd(a, b) = 1 and b is at least 2, the coefficient x reduced modulo b is the modular inverse of a. Use the linked modular inverse calculator to obtain its normalized value.
Are large results exact and private?
Yes. BigInt preserves every integer digit. Inputs are processed in your browser without being uploaded or stored.