Published by Dimitris Kougioumtzis · Updated
Replace (a,b) with (b,a mod b) until b is zero.
Replace the pair by divisor and remainder; each replacement preserves all common divisors.
When to use Euclidean greatest common divisor
Reducing fractions and checking coprimality.
Choosing an alternative
Binary GCD uses shifts; extended Euclid also returns integer coefficients.
Worked example: input and state changes
Example input
48, 18
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": [ 48, 18 ], "active": [] }Step 2: Replace the pair.
State at this checkpoint
{ "values": [ 18, 12 ], "active": [ 0, 1 ] }Step 4: Replace the pair.
State at this checkpoint
{ "values": [ 12, 6 ], "active": [ 0, 1 ] }Step 5: 12 mod 6 = 0.
State at this checkpoint
{ "values": [ 12, 6 ], "active": [ 0, 1 ] }Step 7: Greatest common divisor = 6.
State at this checkpoint
{ "values": [ 6, 0 ], "active": [ 0 ] }
Expected final state
Greatest common divisor = 6.
Complexity and input bounds
Family: Number theory. Time complexity: O(log min(a,b)).
Space complexity: O(1) iterative 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
Handle zero according to the contract, especially the both-zero case.
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 | // Nonnegative integers, not both zero. 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) { while (b != 0) { let r = a % b; a = b; b = r; } return a; } |
Source
Historical presentation of the Euclidean method in a modern scholarly online edition, rather than a modern research paper.
- Elements, Book VII, Proposition 2
Euclid; online edition and commentary by David E. Joyce (c. 300 BCE; modern online edition). Historical text (modern edition).