Extended Euclidean Algorithm Calculator
Our free number theory calculator solves extended euclidean algorithm problems. Get worked examples, visual aids, and downloadable results.
Reviewed by Manoj Kumar, Mathematics Educator
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.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy