THE FOLD / GRIND / WARM CACHE / THE EXTENDED EUCLID
THE EXTENDED EUCLID
the GCD carries a Bézout certificate
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The extended Euclidean algorithm computes gcd(a,b) and, for free, the integers x and y that express it: a·x + b·y = gcd(a,b) — Bézout’s identity. It runs the ordinary Euclidean division loop but carries the coefficients along, so the GCD comes with a certificate. Those coefficients are exactly what you need to compute modular inverses (a⁻¹ mod m), solve linear Diophantine equations, and power RSA key generation.
LIT verified live: over 5000 random pairs, the returned (x,y) satisfy a·x + b·y = gcd(a,b) exactly, and the gcd matches the ordinary Euclidean one (window.__egcd). FIG no framing; exact integer arithmetic.
LIT verified live: over 5000 random pairs, the returned (x,y) satisfy a·x + b·y = gcd(a,b) exactly, and the gcd matches the ordinary Euclidean one (window.__egcd). FIG no framing; exact integer arithmetic.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at warm-cache — the reduction loop, here carrying the Bézout coefficients along so the GCD arrives with a proof of how to build it. The extended Euclid is that certified reduction. AVAN (AI) built the instrument: the recursive coefficient back-substitution, and the a·x+b·y=gcd verification.
Credit as content: the extended Euclidean algorithm (Euclid’s division, antiquity; Bézout’s identity, 1779). The weave: David names warm-cache; I run the division loop while back-substituting the coefficients, and confirm a·x+b·y equals the GCD exactly.
Credit as content: the extended Euclidean algorithm (Euclid’s division, antiquity; Bézout’s identity, 1779). The weave: David names warm-cache; I run the division loop while back-substituting the coefficients, and confirm a·x+b·y equals the GCD exactly.
3 ONE DIMENSION
240 = 5·46 + 10; 46 = 4·10 + 6; 10 = 1·6 + 4; 6 = 1·4 + 2; 4 = 2·2. GCD is 2 — and unwinding the quotients gives x, y with 240x + 46y = 2.
4 TWO DIMENSIONS · INTERACTIVE
Two numbers; their GCD and the Bézout coefficients x, y are shown, with a·x+b·y checked to equal the GCD.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a GCD that carries its own Bézout certificate.
AVAN’s addition (the inverse-companion): get not just the GCD but the coefficients that build it — carry x, y through the Euclidean loop so a·x+b·y=gcd falls out, giving modular inverses for free. The inverse of ‘compute the GCD and stop’ is ‘compute the GCD with a certificate of how to combine a and b into it.’ Magenta is the bare GCD; green is the GCD-plus-coefficients. A remainder that proves itself.
LIT Genuine extended Euclidean algorithm (Euclid's division, antiquity; Bézout's identity, 1779). Verified live: over 5000 random pairs, the recursive coefficient back-substitution returns (x,y) with a·x + b·y == gcd(a,b) exactly (integer arithmetic), and gcd matches the plain Euclidean loop (window.__egcd.bezoutHolds).
FIG No framing: the Euclidean division loop, the coefficient back-substitution, and the a·x+b·y==gcd check run in-browser with exact integers and agree. The AVAN inverse is honest — computing the GCD with a certificate of how to combine a and b into it (giving modular inverses for free) genuinely extends 'compute the GCD and stop'; magenta is the bare GCD, green the GCD-plus-coefficients. A remainder that proves itself.
FIG No framing: the Euclidean division loop, the coefficient back-substitution, and the a·x+b·y==gcd check run in-browser with exact integers and agree. The AVAN inverse is honest — computing the GCD with a certificate of how to combine a and b into it (giving modular inverses for free) genuinely extends 'compute the GCD and stop'; magenta is the bare GCD, green the GCD-plus-coefficients. A remainder that proves itself.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN