Extended Euclidean algorithm

The extended Euclidean algorithm computes the greatest common divisor of two integers and integers expressing that divisor as their linear combination.

Euclidean algorithm: A method for finding the greatest common divisor of two integers by repeated division with remainder. The extended algorithm adds coefficient tracking to this underlying sequence of divisions.
Modular multiplicative inverse: An integer that multiplies a given residue to produce 1 modulo a specified modulus. When an inverse exists, a Bézout coefficient computed here supplies it.
Greatest common divisor: The largest positive integer that divides each of two integers, when at least one is nonzero. This is the quantity the extended algorithm computes alongside its coefficients.
Binary GCD algorithm: A gcd algorithm that uses parity checks, shifts, and subtraction instead of general division. It computes the gcd efficiently but does not directly provide Bézout coefficients.
Bézout's identity: The theorem that the greatest common divisor of two integers is an integer linear combination of them. The algorithm constructs the coefficients whose existence this identity guarantees.
Linear Diophantine equation: An equation in which integer variables satisfy a linear relation with integer coefficients. The algorithm determines whether ax + by = c has integer solutions and helps construct them.
Coprime integers: Integers whose greatest common divisor is 1. For coprime inputs, the algorithm produces a linear combination equal to 1.
Lehmer's GCD algorithm: A gcd algorithm that batches Euclidean steps using leading digits to reduce large-integer division costs. It accelerates Euclidean computations and can be adapted to track coefficients.
Back-substitution: A method that substitutes known equations into earlier equations to express a quantity in desired terms. Reversing the remainder equations recovers the gcd as a combination of the original inputs.
Chinese remainder theorem: A theorem that combines compatible congruences with pairwise coprime moduli into one residue class. Its constructive proofs use modular inverses obtainable from Bézout coefficients.

Linked from 3 pages