Extended Euclidean Algorithm Calculator
Our free number theory calculator solves extended euclidean algorithm problems. Get worked examples, visual aids, and downloadable results.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Extended Euclidean Algorithm Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: gcd(a, b) = ax + by (Extended GCD with Bezout coefficients)
Worked example — gcd(240, 46) = 2 | 240*(-9) + 46*(47) = 2 | x = -9, y = 47
Formula
gcd(a, b) = ax + by (Extended GCD with Bezout coefficients)
The Extended Euclidean Algorithm finds the GCD of two integers a and b while simultaneously computing Bezout coefficients x and y satisfying ax + by = gcd(a,b). It tracks coefficient sequences alongside the standard remainder sequence, terminating when the remainder reaches 0.
Worked Examples
Example 1: Extended Euclidean Algorithm for 240 and 46
Problem:Find gcd(240, 46) and integers x, y such that 240x + 46y = gcd(240, 46).
Solution:Euclidean Algorithm: 240 = 5 * 46 + 10 46 = 4 * 10 + 6 10 = 1 * 6 + 4 6 = 1 * 4 + 2 4 = 2 * 2 + 0 Back-substitution: 2 = 6 - 1*4 2 = 6 - 1*(10 - 1*6) = 2*6 - 10 2 = 2*(46 - 4*10) - 10 = 2*46 - 9*10 2 = 2*46 - 9*(240 - 5*46) = -9*240 + 47*46
Result:gcd(240, 46) = 2 | 240*(-9) + 46*(47) = 2 | x = -9, y = 47
Example 2: Finding Modular Inverse of 17 mod 43
Problem:Use the Extended Euclidean Algorithm to find the inverse of 17 modulo 43.
Solution:Compute gcd(17, 43): 43 = 2 * 17 + 9 17 = 1 * 9 + 8 9 = 1 * 8 + 1 8 = 8 * 1 + 0 gcd = 1, so inverse exists. Back-substitute: 1 = 9 - 1*8 = 9 - (17-9) = 2*9 - 17 = 2*(43-2*17) - 17 = 2*43 - 5*17 17*(-5) + 43*(2) = 1 Inverse = -5 mod 43 = 38 Verify: 17 * 38 = 646 = 15*43 + 1
Result:17^(-1) mod 43 = 38 | Verified: 17 * 38 = 646 = 15*43 + 1
Frequently Asked Questions
What is the Extended Euclidean Algorithm and how does it differ from the standard version?
The Extended Euclidean Algorithm is an augmented version of the classic Euclidean Algorithm that not only computes the greatest common divisor (GCD) of two integers a and b, but also finds integers x and y such that ax + by = gcd(a,b). The standard Euclidean Algorithm only produces the GCD through repeated division, computing a sequence of remainders until reaching zero. The extended version tracks two additional sequences of coefficients alongside the remainders, maintaining the invariant that at each step, the current remainder can be expressed as a linear combination of the original inputs a and b. This additional information is crucial because the coefficients x and y (called Bezout coefficients) have direct applications in modular arithmetic, cryptography, and solving Diophantine equations. The algorithm runs in the same time complexity as the standard version, O(log(min(a,b))) steps, making the extension essentially free in computational terms.
How does the Extended Euclidean Algorithm work step by step?
The algorithm maintains three parallel sequences: remainders (r), and two coefficient sequences (s and t). Initialize: (old_r, r) = (a, b), (old_s, s) = (1, 0), (old_t, t) = (0, 1). At each iteration, compute the quotient q = floor(old_r / r), then simultaneously update all three pairs: new_r = old_r - q*r, new_s = old_s - q*s, new_t = old_t - q*t. The old values become current, and current become new. Continue until r = 0. At termination, old_r contains the GCD, and old_s and old_t are the Bezout coefficients x and y. The key invariant maintained throughout is: old_r = a*old_s + b*old_t and r = a*s + b*t. This invariant can be verified at each step and guarantees correctness. For example, with a=240, b=46: step 1 gives q=5, r=10; step 2 gives q=4, r=6; step 3 gives q=1, r=4; step 4 gives q=1, r=2; step 5 gives q=2, r=0. So gcd=2, with coefficients found through the s,t tracking.
What is Lames theorem about the Euclidean Algorithm?
Lames theorem provides a tight upper bound on the number of division steps in the Euclidean Algorithm. It states that the number of steps to compute gcd(a,b) with a > b > 0 is at most 5 times the number of decimal digits in b. More precisely, if the algorithm requires n division steps, then b must be at least as large as the nth Fibonacci number. This means the Fibonacci numbers represent the worst-case inputs for the Euclidean Algorithm: computing gcd(F_{n+1}, F_n) requires exactly n-1 division steps, the maximum possible for numbers of that size. Gabriel Lame proved this result in 1844, making it one of the earliest analyses of algorithmic complexity. The bound implies that the algorithm runs in O(log b) steps, which is O(n) where n is the number of digits. Since each step involves one integer division, the total time complexity is O(n^2) with standard arithmetic or O(n*log^2(n)) with fast multiplication algorithms. This efficiency is remarkable and makes the algorithm practical for very large numbers used in cryptography.
How is the Extended Euclidean Algorithm used to find modular inverses?
Finding the modular inverse of a modulo n means finding x such that ax mod n = 1, which exists if and only if gcd(a,n) = 1. The Extended Euclidean Algorithm directly solves this: compute gcd(a,n) along with coefficients x and y satisfying ax + ny = 1. Reducing modulo n gives ax mod n = 1, so x mod n is the modular inverse. For example, to find the inverse of 7 modulo 11: the algorithm gives 7(-3) + 11(2) = 1, so the inverse is -3 mod 11 = 8. Indeed, 7*8 = 56 = 5*11 + 1. This is more efficient than using Eulers theorem (computing a^(phi(n)-1) mod n) because it avoids modular exponentiation. In RSA key generation, computing the private key d requires finding the modular inverse of the public exponent e modulo phi(n), making the Extended Euclidean Algorithm a critical component of one of the worlds most widely used cryptographic systems. The algorithm handles arbitrarily large numbers efficiently, which is essential for 2048-bit or 4096-bit RSA keys.
What is the connection between the GCD and the LCM?
The greatest common divisor (GCD) and least common multiple (LCM) of two positive integers a and b are related by the fundamental identity: a * b = gcd(a,b) * lcm(a,b). This means lcm(a,b) = a*b / gcd(a,b), providing an efficient way to compute the LCM using the Euclidean Algorithm for the GCD. The GCD represents the largest number dividing both a and b, while the LCM represents the smallest number that both a and b divide. In terms of prime factorizations, if a = product of p_i^a_i and b = product of p_i^b_i, then gcd uses min(a_i, b_i) for each prime and lcm uses max(a_i, b_i). The identity follows because min + max = a_i + b_i for each prime. This relationship extends to multiple numbers, though the simple product formula only works for two numbers. The LCM appears in adding fractions (finding common denominators), scheduling problems (finding common periods), and in the Chinese Remainder Theorem. The Carmichael function lambda(n) is defined as the LCM of totient values of prime power factors.
How does the algorithm handle negative numbers and zero?
The Extended Euclidean Algorithm handles negative numbers and zero with specific conventions. For zero inputs: gcd(a,0) = |a| with coefficients x=sign(a), y=0, and gcd(0,b) = |b| with x=0, y=sign(b). The convention gcd(0,0) = 0 is standard. For negative inputs, the algorithm works with absolute values and adjusts signs at the end. If the algorithm finds |a|*s + |b|*t = gcd(|a|,|b|), then for negative a, multiply s by -1 to get a*(-s) + b*t = gcd. Similarly for negative b, multiply t by -1. The GCD itself is always non-negative by convention. For modular arithmetic applications, negative Bezout coefficients are common and valid: if ax + by = 1 and x is negative, the modular inverse is x mod b = x + b (or x + kb for the smallest positive representative). Some implementations avoid tracking signs by working with unsigned values throughout and only determining signs at the end based on the parity of the number of steps. The mathematical validity is guaranteed because gcd(a,b) = gcd(|a|,|b|) for all integers a and b.
What are the applications of the Extended Euclidean Algorithm in coding theory?
The Extended Euclidean Algorithm is fundamental in coding theory, particularly for decoding algebraic error-correcting codes. Reed-Solomon codes, used in CDs, DVDs, QR codes, and deep-space communication, require the Extended Euclidean Algorithm for their decoding procedure. The Berlekamp-Massey algorithm and the Sugiyama algorithm (an adaptation of the Extended Euclidean Algorithm) find the error locator polynomial by performing the Extended Euclidean Algorithm on polynomials rather than integers. BCH codes similarly use polynomial GCD computations for decoding. In the key equation of the Peterson-Gorenstein-Zierler decoder, the Extended Euclidean Algorithm solves for the error evaluator polynomial. Convolutional codes used in wireless communications employ Viterbi decoding, which while different in approach, shares mathematical foundations with algebraic coding. The algorithm also appears in lattice-based cryptography, where computing short vectors in lattices uses variants of the Euclidean Algorithm, and in code-based cryptography schemes like McEliece, where decoding Goppa codes requires polynomial GCD operations.
Can the Extended Euclidean Algorithm be parallelized or optimized?
Several optimizations and variants of the Extended Euclidean Algorithm exist for different computational contexts. The binary GCD algorithm (also called Steins algorithm) replaces division with bit shifts and subtraction, which is faster on processors where division is expensive. It computes gcd(a,b) by repeatedly: if both are even, divide both by 2; if one is even, divide it by 2; if both are odd, replace the larger with their difference divided by 2. The binary Extended GCD extends this to find Bezout coefficients. The half-GCD algorithm by Schonhage achieves the theoretically optimal O(n*log^2(n)*log(log(n))) bit complexity for n-bit inputs, compared to O(n^2) for the standard algorithm. Parallelization is challenging because each step depends on the previous quotient, creating a sequential dependency. However, systolic array implementations and sublinear-depth parallel circuits exist for specific applications. For multiple GCD computations, batch processing techniques can share work across instances. In modular arithmetic contexts, Montgomery multiplication and Barrett reduction complement the Extended Euclidean Algorithm by speeding up the modular operations that typically follow inverse computation.
How does the algorithm relate to continued fractions?
The Euclidean Algorithm and continued fractions are intimately connected. The sequence of quotients q_0, q_1, q_2, ... produced by the Euclidean Algorithm when computing gcd(a,b) are exactly the partial quotients in the continued fraction expansion of a/b. The fraction a/b = q_0 + 1/(q_1 + 1/(q_2 + 1/(...))). The convergents p_k/q_k of this continued fraction (the fractions obtained by truncating) are the best rational approximations to a/b with denominators up to q_k. The coefficients s and t tracked by the Extended Euclidean Algorithm are related to the numerators and denominators of these convergents: the convergent p_k/q_k satisfies the recurrence p_k = q_k * p_{k-1} + p_{k-2}, identical to the recurrence for the s and t sequences. This connection explains why the algorithm finds Bezout coefficients: the last non-zero convergent relationship gives the linear combination. Continued fractions also provide the theory of best rational approximations, used in calendar design, gear ratio selection, and the analysis of the three-distance theorem in dynamical systems.
What happens when you apply the Extended Euclidean Algorithm to polynomials?
The Extended Euclidean Algorithm extends naturally from integers to polynomials over any field (such as rational numbers, real numbers, or finite fields). Instead of integer division, polynomial long division is used to find quotients and remainders. Given polynomials f(x) and g(x), the algorithm finds polynomials u(x) and v(x) such that f(x)*u(x) + g(x)*v(x) = gcd(f(x), g(x)), where the GCD is the monic (leading coefficient 1) polynomial of highest degree dividing both f and g. Each step reduces the degree of the remainder by at least 1, so the algorithm terminates in at most deg(f) steps. Applications include: computing partial fraction decompositions in calculus, finding error patterns in Reed-Solomon and BCH decoding, computing resultants and subresultants in computer algebra, solving polynomial Diophantine equations in control theory (for controller design via coprime factorization), and simplifying rational functions. Over finite fields F_p, the polynomial Extended Euclidean Algorithm is used extensively in elliptic curve cryptography and in implementing arithmetic for algebraic geometry codes.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Greatest Common Factor Calculator
Find the GCF (GCD) of two or more numbers using prime factorization and Euclidean algorithm.
🧮Annulus Area Calculator
Calculate annulus area with inputs, formulas, and instant results.
🧮Area Calculator
Calculate area with inputs, formulas, and instant results.
🧮Area of a Rectangle Calculator
Calculate the area, perimeter, and diagonal of a rectangle. Find missing sides from known area. Convert between metric and imperial area units.
🧮Area of Crescent Calculator
Calculate area of crescent with inputs, formulas, and instant results.
🧮Center of Mass Calculator
Calculate center of mass with inputs, formulas, and instant results.
🧮Centroid Calculator
Calculate centroid with inputs, formulas, and instant results.
🧮Chord Length Calculator
Calculate chord length with inputs, formulas, and instant results.