Extended Euclidean Algorithm – Bézout Coefficients

The extended algorithm runs Euclid’s divisions and then back-substitutes to express the gcd as a combination of the inputs. For 240 and 46: 240 = 5×46 + 10, 46 = 4×10 + 6, 10 = 1×6 + 4, 6 = 1×4 + 2, 4 = 2×2 + 0 — gcd 2. Back-substitution rebuilds it: 2 = 6 − 4 = 6 − (10 − 6) = 2×6 − 10 = 2(46 − 4×10) − 10 = 2×46 − 9×10 = 2×46 − 9(240 − 5×46) = 47×46 − 9×240. Check: −2160 + 2162 = 2 ✓, so Bézout coefficients are (s, t) = (−9, 47). The calculator prints the division table and the full back-substitution chain, verifies the identity numerically, and links the machinery to modular inverses: reducing s·a + t·b = g modulo b shows t ≡ a⁻¹ (mod b) whenever g = 1 — the step that constructs RSA private keys. Alternative signed-remainder and recursive table methods are noted.

1. 1

   Enter a and b

   Any integers, e.g. 240 and 46

2. 2

   Run the divisions

   The quotient/remainder ladder is printed

3. 3

   Back-substitute

   Each substitution step rebuilds the gcd combination

4. 4

   Verify Bézout

   −9×240 + 47×46 = 2 is checked numerically

• 1

  Bézout always exists: gcd(a,b) = sa + tb for some integers s, t

• 2

  When gcd = 1, the coefficient of a is its inverse mod b

• 3

  Back-substitution is mechanical — write every remainder swap

• Stopping at the gcd without performing back-substitution

• Sign slips when substituting remainders upward

• Forgetting to verify sa + tb reproduces the gcd

• Misreading which coefficient inverts which input