Bézout's identity

For integers a and b, their greatest common divisor is an integer linear combination of a and b: gcd(a,b)=ax+by for some integers x and y.

Extended Euclidean algorithm: An algorithm that computes a greatest common divisor and coefficients expressing it as a linear combination of two inputs. It finds the coefficients x and y in Bézout's identity by reversing the Euclidean algorithm.
Linear congruence: A congruence of the form ax≡b (mod m), asking when the two sides differ by a multiple of m. Bézout's identity shows ax≡b (mod m) is solvable exactly when gcd(a,m) divides b.
Greatest common divisor: The largest positive integer dividing each of two integers, with sign conventions extending the definition to zero inputs. It is the specific integer represented by the linear combination.
Bézout coefficients: Integers x and y satisfying ax+by=gcd(a,b) for a given pair of integers a and b. They are the witnesses whose existence Bézout's identity asserts.
Euclidean algorithm: A procedure for finding the greatest common divisor of two integers through repeated division with remainder. Its remainder equations provide the steps that the extended algorithm reverses.
Modular multiplicative inverse: An integer that multiplies a given residue to 1 modulo a specified modulus. When gcd(a,m)=1, the identity ax+my=1 makes x an inverse of a modulo m.
Divisibility: The relation in which one integer is a factor of another with an integer quotient. The gcd is defined through common divisors, while the identity also yields divisibility tests.
Greatest common divisor of 12 and 8: The greatest common divisor of 12 and 8 is 4. The equation 12(1)+8(-1)=4 gives a simple certificate of the identity.
Euclidean division: The representation of an integer as a divisor times a quotient plus a remainder smaller in magnitude than the divisor. Repeated division supplies the equations used to derive the linear combination.
Chinese remainder theorem: A theorem describing simultaneous solutions to congruences with pairwise coprime moduli. Bézout coefficients help construct solutions when combining congruences with coprime moduli.

Linked from 10 pages