Extended Euclidean Algorithm

Dividing two integers repeatedly finds their greatest common divisor. Keeping two extra coefficients turns that result into an identity: the gcd is an integer combination of the original inputs. Those coefficients explain modular inverses without trying every possible multiplier. The experiment exposes every subtraction, including the initial quotient zero when the first magnitude is smaller.

Reproduce the row changes

Open the Extended Euclidean Algorithm explorer. These instructions use its actual controls and accepted inputs. The selected step counts completed divisions, not table rows; the two seed rows are already present at step zero.

1. Press Reset experiment. First integer a is 252, Second integer b is 198, and Division step is 0. The gcd certificate reads Pending. The strip is explicitly a preview of 252=1×198+54.
2. Press Next. The current row becomes 198 with coefficients (0,1); the next row becomes 54 with (1,−1). The first subtraction is now committed.
3. Set Division step to 2. Check the current row (54,1,−1) and next row (36,−3,4). The applied quotient is 3. The last ledger column independently displays ax+by for each row.
4. Press Finish. Check gcd 18, x=4, y=−5 and ax+by=18. The inverse panel reads No inverse. Press Previous: step 3 has current 36 and next 18, and the final certificate returns to Pending. Press Start to restore step 0 without changing the inputs.
5. Choose Coprime example. Press Next once to observe the quotient-zero division, then Finish. Check gcd 1, coefficients (11,−6), inverse 11 and residue check 1. Select a generated ledger row to revisit that division.
6. Choose Signed example and Finish. The magnitude divisions are unchanged, but x is −11 and the inverse is 53. The identity still uses the entered a=−35. Choose Shared-factor example to return to 252 and 198 at step 0.
7. Clear First integer a. The input error replaces the calculation, including its ledger and old inverse. Reset experiment restores the default valid inputs. Spaces, fractional inputs and line breaks also produce errors.
8. Set both integer fields to 0. Observe the Zero pair convention, gcd 0 and coefficients (0,0), with no divisions. No greatest positive common divisor is claimed. Reset experiment returns to the starting exercise.

The strip's width is rescaled for each displayed dividend. Indigo represents q full divisor copies and amber represents the remainder. A large quotient is grouped into one labelled block. Compare the printed values across divisions; absolute pixel lengths do not share a fixed unit. At narrow widths, scroll the ledger within its own table area.