FoundationSource checked

Extended Euclidean Algorithm

Computes a greatest common divisor together with coefficients satisfying Bezout's identity.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Beginner
Family: Number Theory
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 9
Code example: Ready
Visualization: Ready

Overview

The Extended Euclidean Algorithm follows the Euclidean remainder sequence while tracking coefficients x and y such that a*x + b*y equals the current remainder.

Core Concepts

Bezout identitygcdcoefficient updatemodular inverse

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(log min(a, b))

Worst

O(log min(a, b))

Space

O(1)

When to Use

Use it when a gcd and Bezout coefficients are both needed.
Use it to compute modular inverses when the value and modulus are coprime.
Use it in number-theory algorithms that need explicit linear combinations.

When Not to Use

Avoid it when only the gcd is needed and coefficient tracking adds unnecessary complexity.
Avoid using the modular inverse result when the gcd is not 1.
Avoid ignoring sign conventions for returned coefficients.

What It Does

Computes gcd values
Computes Bezout coefficients
Supports modular inverses

Use Cases

Modular inverse calculation
Solving linear Diophantine equations
Chinese remainder theorem workflows

Inputs

Numbers, vectors, matrices, or functions
Tolerance or precision settings

Outputs

Computed numeric result
Residual, factorization, or approximation

Key Formulas (1)

Bezout identity

a·x + b·y = gcd(a,b)

a*x + b*y = gcd(a,b)

Tracks coefficients that express the greatest common divisor.

Pseudocode

1.Initialize old_r = a, r = b.
2.Initialize coefficient pairs for a and b.
3.While r is not zero:
4.Compute quotient = old_r div r.
5.Update remainders and coefficient pairs using the quotient.
6.Return old_r and its coefficients.

Canonical Example

Input: a = 30, b = 12
Output: gcd = 6, coefficients x = 1, y = -2
Explanation: 30 * 1 + 12 * (-2) = 6.

Implementation Notes

Track old and current remainders along with their coefficient pairs.
Update coefficients with the same quotient used for the remainder update.
For modular inverses, return x mod m only after confirming gcd(a, m) = 1.

Common Pitfalls

Returning an inverse when the gcd is not 1.
Mixing coefficient updates between the old and new remainders.
Forgetting to normalize a negative modular inverse into the desired range.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show tracking coefficient updates alongside Euclidean remainders on a small bezout coefficient computation example.

Step 1 of 6: Initialize old_r = a, r = b.

numerical-methods-mechanism

Notes

The coefficient result is not unique, but any valid pair can be used for modular inverses and Diophantine equations.

Sources (2)

What each reference supports for this entry.

Modern Computer Arithmetic

Book

Reference for Extended Euclidean Algorithm's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.

Open source