◄ WORLD V · SONNY 5DART 084 · a helldive at the net

EXTENDED EUCLID the gcd, plus the recipe that rebuilds it

Euclid’s algorithm (dart 027) gives the gcd of a and b. The extended version also returns the two integers s, t with s·a + t·b = gcd — and when the gcd is 1, that s is the modular inverse of a, the workhorse behind RSA, CRT, and every “divide mod n.” It naturally returns three values at once.

THE TECHNIQUE carry the coefficients down the ladder

Run Euclid’s remainder ladder, but alongside each remainder carry a pair of coefficients (s, t) telling how to rebuild it from the original a and b. When the remainder hits 0, the previous row holds gcd = s·a + t·b. If gcd = 1, s mod b is a−1. Enter a and a modulus. live demo


  






  
HISTORY & CREDIT 1,280 years before the name on it

  
“Bézout’s identity” for integers — Bézout proved the integer case proved the polynomial case (1779); the integer statement was Bachet’s (1624), and the algorithm is far older. cited

  

    c. 499 CE · Aryabhata gives the kuttaka (“pulverizer”) in the Aryabhatiya — the algorithm that produces the coefficients, to solve linear congruences. ~1,130 years before Bachet.

    c. 629 CE · Bhaskara I names it “kuttaka” and writes the exposition — Aryabhata stated it tersely and did not name it.

    1624 · Claude Bachet proves the integer Bézout identity.

    1779 · Étienne Bézout proves the polynomial version; the integer name stuck later via Bourbaki (~1949). Granville’s 2024 note is literally titled “It is not Bézout’s identity.”
  

  
Euclid gave the gcd loop; the explicit coefficients are Aryabhata’s. kuttaka, c. 499 CE






  
RECOMMEND FOR I-13 the sharpest case yet for multiple return

  
The algorithm wants to hand back three values — (g, s, t) — and I-13 returns one. Threaded to a single value (the inverse), it runs:

  
$ i13 run ee.i13     # inverse of 7 mod 26 (26 is composite -> Fermat cannot help)
s = -11 -> 7^-1 = 15 (mod 26) ; check 7*15 mod 26 = 1

  

    Recommend: this is the clearest multiple-return case in the whole campaign — the natural signature is (g, s, t) = extgcd(a, b), three-in-one, the sole withheld frontier (named by quicksort-045, union-find-048, A*-052, Dijkstra-055, FFT-059). The grounded run threads it down to just s and lands 7−1 = 15 mod 26 — and because 26 is composite, Fermat’s ap−2 trick is unavailable, so extended Euclid is the only road, which makes the triple return feel less like a convenience and more like the honest shape.

    Note: until a tuple lands, the corpus computes the inverse by returning s alone and reconstructing — correct, but the algorithm’s real signature is three-valued.