# Extended Euclidean GCD Solver Compute the GCD of two numbers and find Bezout coefficients using the Extended Euclidean algorithm with clear step-by-step results. --- - **Canonical URL:** https://dothecalculation.com/calculators/euclidean-algorithm-calculator - **Category:** Math calculators - **Publisher:** Do The Calculation (https://dothecalculation.com) - **Cost:** Free, no account or sign-up required - **Privacy:** Runs entirely in the browser; inputs are never sent to a server - **Methodology:** https://dothecalculation.com/methodology --- ## Extended Euclidean GCD Solver Compute the Greatest Common Divisor (GCD) of two numbers and find Bézout identity coefficients step-by-step. - Standard Euclidean division steps - Bézout coefficients (x, y) - Linear Diophantine equation values ## Understanding the Euclidean Algorithm and Greatest Common Divisors The Euclidean algorithm is an ancient, highly efficient method for computing the greatest common divisor (GCD) of two integers — the largest positive integer that divides both numbers without leaving a remainder. First described by the Greek mathematician Euclid in his Elements around 300 BC, the algorithm is based on the principle that the GCD of two numbers also divides their difference. This property allows us to systematically reduce the size of the numbers until the remainder is zero, at which point the last non-zero divisor is the GCD. While the standard Euclidean algorithm is useful for finding the GCD, its extension — the Extended Euclidean Algorithm — is even more powerful. It not only finds the GCD but also calculates integers \(x\) and \(y\) that satisfy Bézout's identity: \(ax + by = \gcd(a, b)\). These coefficients are crucial in modular arithmetic and cryptography, where they are used to compute modular multiplicative inverses. This calculator provides the complete step-by-step division steps for both the standard and extended Euclidean algorithms, demonstrating how to express the GCD as a linear combination of the inputs. ## How to Use This Calculator Enter two positive integers \(a\) and \(b\). The calculator runs the standard Euclidean algorithm to find the GCD, then works the Extended Euclidean algorithm backward to find Bézout coefficients \(x\) and \(y\) such that \(ax + by = \gcd(a, b)\), and reports the modular inverse of \(a\) modulo \(b\) when it exists. ## Mathematical Formulation of the Extended Euclidean Algorithm Given two integers \(a\) and \(b\) (where \(a \geq b\)), the Euclidean algorithm uses successive integer division with remainders: $$a = q_1 b + r_1$$ $$b = q_2 r_1 + r_2$$ $$r_1 = q_3 r_2 + r_3$$ This process continues until a remainder \(r_k\) is zero. The last non-zero remainder \(r_{k-1}\) is \(\gcd(a, b)\). To find Bézout's coefficients \(x\) and \(y\), the Extended Euclidean algorithm works backward. We write the remainder from each step in terms of the dividend and divisor, substituting equations upward to express \(\gcd(a, b)\) as: $$\gcd(a, b) = ax + by$$ This calculator maintains tabulations of coefficients \(s_i\) and \(t_i\) at each step to demonstrate how \(x\) and \(y\) are calculated. ## Worked Case Study: Finding the GCD of 240 and 46 Let us compute the GCD of \(a = 240\) and \(b = 46\) and express it as a linear combination \(240x + 46y\). First, we perform successive division steps: 1. \(240 = 5 \times 46 + 10\) (remainder \(r_1 = 10\)) 2. \(46 = 4 \times 10 + 6\) (remainder \(r_2 = 6\)) 3. \(10 = 1 \times 6 + 4\) (remainder \(r_3 = 4\)) 4. \(6 = 1 \times 4 + 2\) (remainder \(r_4 = 2\)) 5. \(4 = 2 \times 2 + 0\) (remainder is 0) The last non-zero remainder is 2, so \(\gcd(240, 46) = 2\). Now, we work backward to find Bézout's coefficients: $$2 = 6 - 1 \times 4$$ Substitute \(4 = 10 - 1 \times 6\): $$2 = 6 - 1 \times (10 - 1 \times 6) = 2 \times 6 - 1 \times 10$$ Substitute \(6 = 46 - 4 \times 10\): $$2 = 2 \times (46 - 4 \times 10) - 1 \times 10 = 2 \times 46 - 9 \times 10$$ Substitute \(10 = 240 - 5 \times 46\): $$2 = 2 \times 46 - 9 \times (240 - 5 \times 46) = -9 \times 240 + 47 \times 46$$ Thus, Bézout's coefficients are \(x = -9\) and \(y = 47\), satisfying \(-9(240) + 47(46) = 2\). ## Cryptographic Applications: Modular Multiplicative Inverse The Extended Euclidean algorithm is the primary tool used to compute modular multiplicative inverses in cryptography, such as in the RSA algorithm. If \(a\) and \(m\) are coprime (\(\gcd(a, m) = 1\)), there exists an integer \(x\) such that \(ax \equiv 1 \pmod{m}\). By applying the Extended Euclidean algorithm, we find \(x\) and \(y\) such that \(ax + my = 1\). Taking this equation modulo \(m\) gives \(ax \equiv 1 \pmod{m}\), meaning the Bézout coefficient \(x\) (adjusted to be positive) is the modular inverse of \(a\) modulo \(m\). ## Related Calculators To factor a number into its prime components directly (an alternative, slower way to find a GCD), use the [prime factorization calculator](/calculators/prime-factorization-calculator). For arithmetic with a fixed modulus rather than finding an inverse, see the [modular arithmetic calculator](/calculators/modular-arithmetic-calculator). ## Frequently asked questions ### What is the Euclidean algorithm? The Euclidean algorithm is an efficient method for computing the Greatest Common Divisor (GCD) of two integers by repeatedly replacing the larger number with the remainder of division. ### What is the Extended Euclidean algorithm? The Extended Euclidean algorithm is an extension of the standard algorithm that also computes integers x and y (Bézout coefficients) satisfying ax + by = gcd(a, b). ### What are Bézout's coefficients? They are the integers x and y in Bézout's identity ax + by = gcd(a, b), representing the GCD as a linear combination of the two inputs. ### What is a modular multiplicative inverse? The modular inverse of a modulo m is an integer x such that (a × x) mod m = 1. It exists only if a and m are coprime. ### How does the Euclidean algorithm relate to prime factorization? While prime factorization can be used to find the GCD by comparing prime factors, it is computationally slow. The Euclidean algorithm finds the GCD much faster without factoring. ### What does coprime mean? Two integers are coprime (or relatively prime) if their greatest common divisor is 1: gcd(a, b) = 1. ### Why does the Euclidean algorithm always terminate? It must terminate because the remainders form a strictly decreasing sequence of non-negative integers (r₁ > r₂ > r₃ ... ≥ 0), which must eventually reach zero. ### Can the Euclidean algorithm handle negative numbers? Yes. The GCD of negative numbers is calculated by taking their absolute values: gcd(a, b) = gcd(|a|, |b|). ### What is the complexity of the Euclidean algorithm? The algorithm has logarithmic complexity, O(log(min(a, b))). Lamé's Theorem states that the number of steps is never more than 5 times the number of digits of the smaller number. ### What is a linear Diophantine equation? A Diophantine equation of the form ax + by = c has integer solutions for x and y if and only if the GCD of a and b divides c. ### How are Bézout coefficients kept within bounds? Bézout coefficients satisfy |x| < |b|/gcd(a,b) and |y| < |a|/gcd(a,b). If a solution is found, other solutions can be written as x + k(b/d) and y − k(a/d). ### Is the GCD commutative? Yes, gcd(a, b) = gcd(b, a) for any integers a and b. ## Related concepts - **Bézout's Identity** — A theorem stating that the GCD of two integers can be expressed as a linear combination of those integers with integer coefficients. - **Modular Multiplicative Inverse** — An integer that acts as a reciprocal under modular arithmetic multiplication: ax ≡ 1 (mod m). - **Diophantine Equations** — Polynomial equations for which only integer solutions are sought, solvable using Euclidean coefficients. ## Related guides - [Fraction Operations Guide: Add, Subtract, Multiply, Divide](https://dothecalculation.com/blog/math/fraction-operations-guide) — Learn the rules for adding, subtracting, multiplying, and dividing fractions, with simplification steps and live DTC calculator workflows. ## Related calculators - [Circle Equation & Geometry Solver](https://dothecalculation.com/calculators/circle-solver) — Convert between standard and general circle equation forms, find centers and radii, and compute areas with this free geometry solver. - [Modular Arithmetic & Congruence Solver](https://dothecalculation.com/calculators/modular-arithmetic-calculator) — Perform modular addition, multiplication, and exponentiation, and solve linear modular congruence equations with clear steps. - [Mixed Number Fraction Calculator](https://dothecalculation.com/calculators/mixed-number-calculator) — Add, subtract, multiply, divide, and simplify mixed number fractions with clear step-by-step conversions and instant results. - [Prime Number Checker & List Generator](https://dothecalculation.com/calculators/prime-number-calculator) — Check primality, find the next prime, and generate prime numbers within a custom range using fast sieve methods instantly. - [Decimal to Fraction Calculator](https://dothecalculation.com/calculators/decimal-to-fraction-calculator) — Use our free decimal to fraction calculator to convert any decimal to a fraction. Shows step-by-step work for terminating and repeating decimals. - [Fraction to Decimal Calculator](https://dothecalculation.com/calculators/fraction-to-decimal-calculator) — Convert fractions to decimals with step-by-step long division and repeating decimal bar notation shown clearly and instantly. --- _This mathematical solver is designed for academic, engineering, and educational analysis. Rounding errors, numerical tolerances, or algorithm constraints might apply near poles, boundary conditions, or complex coordinate spaces. Always verify critical computations independently._ --- _Source: [Do The Calculation](https://dothecalculation.com/calculators/euclidean-algorithm-calculator). Quote freely with attribution and a link to this page._