Published by Dimitris Kougioumtzis · Updated
Find gcd(a,b) and signed coefficients x,y satisfying ax + by = gcd(a,b).
Track every Euclidean remainder as a combination of the original inputs, ending with coefficients satisfying a*x+b*y=gcd(a,b).
When to use Extended Euclidean algorithm
Modular inverses and small Diophantine equations.
Choosing an alternative
Ordinary GCD supplies the divisor without coefficients.
Worked example: input and state changes
Example input
240,46
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 240, 46, 1, 0, 0, 1 ], "active": [] }Step 2: Quotient 4; state: old/new remainder, old/new x coefficient, old/new y coefficient.
State at this checkpoint
{ "values": [ 10, 6, 1, -4, -5, 21 ], "active": [ 0, 2, 4 ] }Step 3: Quotient 1; state: old/new remainder, old/new x coefficient, old/new y coefficient.
State at this checkpoint
{ "values": [ 6, 4, -4, 5, 21, -26 ], "active": [ 0, 2, 4 ] }Step 5: Quotient 2; state: old/new remainder, old/new x coefficient, old/new y coefficient.
State at this checkpoint
{ "values": [ 2, 0, -9, 23, 47, -120 ], "active": [ 0, 2, 4 ] }Step 6: 240 × -9 + 46 × 47 = 2.
State at this checkpoint
{ "values": [ 2, 0, -9, 23, 47, -120 ], "active": [], "result": 2, "coefficients": [ -9, 47 ] }
Expected final state
240 × -9 + 46 × 47 = 2.
Complexity and input bounds
Family: Number theory. Time complexity: O(log min(a,b)).
Space complexity: O(1) remainder and coefficient state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Two integers from 0 to 9999, not both zero.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Bezout coefficients are not unique; verify the identity instead of one arbitrary coefficient pair.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 | // a,b in 0–9999, not both zero. Returns gcd; output[0],output[1] are signed Bézout coefficients satisfying a*x+b*y=gcd. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, b, output) { let oldR = a; let r = b; let oldS = 1; let s = 0; let oldT = 0; let t = 1; while (r != 0) { let q = Math.floor(oldR / r); let nextR = oldR - q * r; let nextS = oldS - q * s; let nextT = oldT - q * t; oldR = r; r = nextR; oldS = s; s = nextS; oldT = t; t = nextT; } output[0] = oldS; output[1] = oldT; return oldR; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book.