Extended Euclidean Algorithm Calculator
Our free number theory calculator solves extended euclidean algorithm problems. Get worked examples, visual aids, and downloadable results.
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:\n240 = 5 * 46 + 10\n46 = 4 * 10 + 6\n10 = 1 * 6 + 4\n6 = 1 * 4 + 2\n4 = 2 * 2 + 0\n\nBack-substitution:\n2 = 6 - 1*4\n2 = 6 - 1*(10 - 1*6) = 2*6 - 10\n2 = 2*(46 - 4*10) - 10 = 2*46 - 9*10\n2 = 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):\n43 = 2 * 17 + 9\n17 = 1 * 9 + 8\n9 = 1 * 8 + 1\n8 = 8 * 1 + 0\n\ngcd = 1, so inverse exists.\nBack-substitute: 1 = 9 - 1*8 = 9 - (17-9) = 2*9 - 17\n= 2*(43-2*17) - 17 = 2*43 - 5*17\n\n17*(-5) + 43*(2) = 1\nInverse = -5 mod 43 = 38\nVerify: 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.
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.