Extended Euclidean Algorithm

Number Theory · Axiom Academy

LESSON Extended Euclidean Algorithm Finding coefficients for Bezout's identity and computing modular inverses 1. The Goal: Bezout's Identity The standard Euclidean algorithm finds gcd(a,b). The Extended Euclidean Algorithm goes further: it finds integers x and y such that: This equation is called Bezout's identity . The coefficients x and y are called Bezout coefficients . Verify: 252(-2) + 105(5) = -504 + 525 = 21 2. The Back-Substitution Method One approach is to run the standard Euclidean algorithm, record all equations, then substitute backwards. 35 = 15(2) + 5 → 5 = 35 - 15(2) Working backwards from equation 1: This method works but becomes tedious for larger numbers. The table method is more systematic. The table method tracks coefficients systematically as we perform the algorithm. We maintain columns for quotients, remainders, and coefficients x and y. Initialize: x₀ = 1, x₁ = 0, y₀ = 0, y₁ = 1 At each step: xᵢ = xᵢ₋₂ - qᵢ₋₁ · xᵢ₋₁ Similarly: yᵢ = yᵢ₋₂ - qᵢ₋₁ · yᵢ₋₁ The previous row gives gcd and coefficients 4. Complete Example: gcd(252, 105) Let's work through a complete example using the table method to find gcd(252, 105) and express it as 252x + 105y. 5. Application: Finding Modular Inverses One of the most important applications of the Extended Euclidean Algorithm is finding modular multiplicative inverses , which are essential in cryptography.

This is the written version of the interactive lesson above. See the full Number Theory course.