Extended Euclidean algorithm: the idea
Prerequisites: Euclid’s algorithm and integer linear combinations.
Extended Euclid retains the remainder reduction and tracks its algebra. For original inputs A and B, each current remainder r is stored alongside coefficients x and y such that r = A × x + B × y. Subtracting q times the next remainder updates all three quantities together. When the next remainder becomes zero, the surviving coefficients express the GCD as an integer linear combination of A and B.
Try it
Use 252 and 105. The result can be written 21 = 252 × (−2) + 105 × 5. Try coprime inputs such as 35 and 12; the final combination equals 1.
Reading the display
Two rows hold successive remainders and their coefficients. Every recorded row satisfies A × x + B × y = r. The quotient determines the next simultaneous update.
Time and memory
O(log max(A,B)) quotient steps for positive inputs; O(1) stored integers under the bounded-arithmetic model.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
Used in modular inverses and integer equations. Coefficients need not be unique. Negative coefficients are valid even though the inputs here are nonnegative. Both-zero inputs return GCD 0 with a valid zero identity.
Continue exploring
- Euclidean algorithm — Find a greatest common divisor through successive remainders.
- Sieve of Eratosthenes — Cross out multiples and reveal every prime up to a limit.
- Binary exponentiation — Build large powers by repeated squaring and halving.