Extended Euclidean Algorithm

Replay exact integer divisions, track Bézout coefficients and discover when a gcd certificate produces a modular inverse.

Extended Euclidean Algorithm

A gcd with a checkable certificate

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.

Keep the same common divisors

Start with nonnegative magnitudes u=|a| and v=|b|. When v is positive, divide u by v to obtain an integer quotient q and a remainder w with 0 ≤ w < v. A number divides both u and v exactly when it divides both v and w=u−qv. Replacing the pair with (v,w) therefore preserves the gcd.

u = qv + w

gcd(u, v) = gcd(v, w)

r = ax + by

w = a(x_u − qx_v) + b(y_u − qy_v)

The final nonzero remainder is the gcd. Its x and y are Bézout coefficients: ax+by=gcd(a,b). The new zero row also satisfies its identity, but its coefficients certify zero, not the gcd. The current and next rows in the explorer make that distinction visible.

For negative inputs, the divisions still use absolute values. The initial coefficient of a is −1 when a is negative, and similarly for b. Thus the ledger always refers to the signed numbers you entered. It does not change their order or require negative remainders.

Predict the certificate for 252 and 198

This original example begins with 252=1×252+0×198 and 198=0×252+1×198. Subtract a quotient times the second row from the first to create each new row. Calculate the following table before pressing Finish.

Division	New remainder	x	y	Check with original inputs
252 = 1×198 + 54	54	1	−1	252−198=54
198 = 3×54 + 36	36	−3	4	−756+792=36
54 = 1×36 + 18	18	4	−5	1008−990=18
36 = 2×18 + 0	0	−11	14	−2772+2772=0

For example, the second update gives x=0−3×1=−3 and y=1−3×(−1)=4. After all four divisions, the current row is 18 with coefficients (4,−5), while the next row is zero. The completed certificate is 18=4×252−5×198. Checking only that both inputs are divisible by 18 would not by itself exclude a larger common divisor. The identity does: every common divisor must divide this combination.

Turn a certificate into an inverse

Now use a=35 and b=64. The quotient sequence is 0,1,1,4,1,5. The initial zero is a real division, 35=0×64+35. Subsequent remainders are 29,6,5,1,0. The final identity is 1=11×35−6×64, so 11×35 leaves residue 1 modulo 64. The inverse is 11.

If a becomes −35, the coefficient of a becomes −11: (−35)×(−11)+64×(−6)=1. The explorer reports the least nonnegative residue of −11 modulo 64, which is 53. Direct multiplication gives (−35)×53=−1855=−29×64+1.

Why a gcd of one matters

For a positive modulus b greater than 1, a has a multiplicative inverse exactly when gcd(a,b)=1. A Bézout identity ax+by=1 gives ax≡1 modulo b. Conversely, if az≡1 modulo b, then az−kb=1 for some integer k; any common divisor of a and b must divide 1. A non-coprime pair such as 252 and 198 cannot pass that test.

The coefficient pair need not be unique. For g=gcd(a,b)>0, replacing (x,y) with (x+t b/g, y−t a/g) preserves ax+by=g for any integer t. With 35 and 64, (75,−41) works just as (11,−6) does. The algorithm chooses one deterministic pair; normalization makes the modular inverse unique in 0 through b−1.

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.

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.
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.
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.
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.
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.
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.
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.
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.

Exact small integers, explicit conventions

The experiment accepts an optional + or - followed by one to three digits from 0 through 9. Thus its numerical domain is −999 through 999, with leading zeros allowed. Raw entries are retained: +035 is valid, while 1000, 2.5, 1e2, spaces and line breaks are rejected. There is no rounding, clamping or automatic substitution of zero. Within this bound, all displayed integer arithmetic is exact in JavaScript's number representation.

If b=0 and a is nonzero, |a| is already the gcd; no division occurs. If a=0 and b is nonzero, the unswapped trace includes one quotient-zero division. Equal nonzero magnitudes take one division.
For (0,0), every positive integer is a common divisor, so a greatest positive one does not exist. The explorer uses the common computational convention gcd(0,0)=0 and selects (0,0) as a certificate pair. That convention is stated separately from the ordinary gcd argument.
The inverse application uses the original second input only when b>1. A negative b, zero or modulus 1 produces Not applicable. A valid positive modulus with gcd greater than 1 produces No inverse, a mathematical outcome rather than an input error.
Before completion, the current remainder generally is not the gcd. Pending output prevents a partially replayed identity from being presented as a finished certificate. The two final coefficient rows have different roles even though both satisfy ax+by=r.

For nonzero inputs, remainder reduction gives a logarithmic number of divisions in the smaller magnitude, after any initial quotient-zero step. The cost of division on very large integers is a separate bit-complexity question. This tiny integer teaching tool is neither a large-integer implementation nor a secure encryption system.

Connections to modular computation

The Chinese Remainder Theorem combines residue conditions, often using an inverse. RSA Encryption uses a modular inverse during key generation. Shamir Secret Sharing uses field inverses for interpolation. This explorer isolates the arithmetic certificate behind those operations; it does not implement their full protocols.

Sources for the method

These educational sources support the remainder method, coefficient invariant and inverse criterion. The 252/198 and 35/64 traces above were calculated for this article; they are not examples attributed to either source. Input limits and the all-zero display convention are choices of this experiment.

Ben Lynn, Stanford: Euclid's Algorithm — division and remainder, extended back substitution, a bound on remainder reduction and the family of integer coefficient solutions.
MIT 18.310, algebra lecture notes — pages 1–3 develop gcd identities and coefficient updates; page 5 connects a coprime residue's Bézout identity to its modular inverse.

Extended Euclidean Algorithm