Extended Euclidean Algorithm Calculator
Our free number theory calculator solves extended euclidean algorithm problems. Get worked examples, visual aids, and downloadable results.
Calculator
Adjust values & calculateEuclidean Algorithm Steps
Extended Algorithm Table
| Step | q | r | s | t |
|---|---|---|---|---|
| 0 | - | 240 | 1 | 0 |
| 1 | 5 | 46 | 0 | 1 |
| 2 | 4 | 10 | 1 | -5 |
| 3 | 1 | 6 | -4 | 21 |
| 4 | 1 | 4 | 5 | -26 |
| 5 | 2 | 2 | -9 | 47 |
| 6 | final | 2 | -9 | 47 |
Back-Substitution
General Solution Family
x = -9 + (23)k, y = 47 - (120)k
| k | x | y |
|---|---|---|
| -3 | -78 | 407 |
| -2 | -55 | 287 |
| -1 | -32 | 167 |
| 0 | -9 | 47 |
| 1 | 14 | -73 |
| 2 | 37 | -193 |
| 3 | 60 | -313 |
Formula
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.
Last reviewed: December 2025
Worked Examples
Example 1: Extended Euclidean Algorithm for 240 and 46
Example 2: Finding Modular Inverse of 17 mod 43
Background & Theory
The Extended Euclidean Algorithm Calculator applies the following established principles and formulas. Mathematics rests on a hierarchy of number systems, each extending the previous. The natural numbers (1, 2, 3, ...) support counting and ordering. The integers add negative values and zero, enabling subtraction without restriction. The rational numbers, expressible as p/q where p and q are integers and q is nonzero, close the system under division. The real numbers fill the gaps left by irrationals such as the square root of 2 or pi, forming a complete ordered field. The complex numbers, written as a + bi where i is the square root of negative one, complete the algebraic closure of the reals and allow every polynomial to have a root. Prime factorization states that every integer greater than one is uniquely expressible as a product of primes, a result known as the Fundamental Theorem of Arithmetic. Computing the greatest common divisor (GCD) of two integers relies most efficiently on the Euclidean algorithm: repeatedly replace the larger number with the remainder when it is divided by the smaller, until the remainder is zero. The last nonzero remainder is the GCD. The least common multiple (LCM) follows from the identity LCM(a, b) = |a * b| / GCD(a, b). Modular arithmetic defines equivalence classes of integers that share the same remainder under division by a modulus n. Fermat's Little Theorem and Euler's Theorem arise from this structure and underpin modern cryptography. Logarithms are the inverses of exponential functions. If b raised to the power x equals y, then the logarithm base b of y equals x. The natural logarithm uses base e, approximately 2.71828. Combinatorics counts arrangements and selections. The number of ordered arrangements (permutations) of r objects from n distinct objects is nPr = n! / (n - r)!. The number of unordered selections (combinations) is nCr = n! / (r! * (n - r)!). Pascal's triangle arranges these binomial coefficients so that each entry equals the sum of the two entries directly above it. The Fibonacci sequence, defined by F(1) = 1, F(2) = 1, and F(n) = F(n-1) + F(n-2), appears throughout nature and connects deeply to the golden ratio via Binet's formula.
History
The history behind the Extended Euclidean Algorithm Calculator traces back through the following developments. Mathematics as a systematic discipline traces to ancient Mesopotamia. Babylonian clay tablets dating to around 1800 BCE demonstrate knowledge of quadratic equations, Pythagorean triples, and base-60 arithmetic, suggesting a practical mathematical tradition far preceding Greek formalism. Euclid of Alexandria compiled the Elements around 300 BCE, establishing the axiomatic method that would define rigorous mathematics for over two thousand years. His work organized plane geometry, number theory, and proportion into logically chained propositions derived from a small set of postulates. The algorithm bearing his name for computing GCDs appears in Book VII and remains in use today. In the 9th century, the Persian scholar Muhammad ibn Musa Al-Khwarizmi wrote Al-Kitab al-mukhtasar fi hisab al-jabr wal-muqabala, the treatise whose title gave algebra its name. He systematized the solution of linear and quadratic equations and described procedures that operated on unknowns as objects, a conceptual leap away from purely numerical calculation. Rene Descartes introduced coordinate geometry in 1637 by uniting algebra and Euclidean geometry, allowing curves to be studied through equations. This synthesis set the stage for calculus. Isaac Newton and Gottfried Wilhelm Leibniz independently developed calculus during the 1660s and 1670s, triggering a priority dispute that lasted decades and divided British and Continental mathematicians. Carl Friedrich Gauss proved the Fundamental Theorem of Algebra in 1799, showing that every nonconstant polynomial has at least one complex root. His Disquisitiones Arithmeticae of 1801 established modern number theory. David Hilbert's formalist program at the turn of the 20th century sought to place all of mathematics on an explicit axiomatic foundation, a project that Kurt Godel's incompleteness theorems of 1931 showed to be fundamentally limited. Alan Turing's work in the 1930s on computability introduced the theoretical model of the stored-program computer and linked mathematical logic directly to the limits of algorithmic calculation. His proof that no algorithm can decide in general whether an arbitrary program will halt or run forever placed fundamental boundaries on what mathematics can mechanically determine, and it opened the discipline now known as theoretical computer science.
Frequently Asked Questions
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.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy