Bézout's identity
ProvedFamousTheorems.bezout_identityBézout's identity.
In a principal ideal domain with a chosen gcd, for any there exist with
The gcd is not merely a common divisor of largest size — it is an explicit integer combination of the two arguments. That is the whole content: divisibility facts about become statements about the ideal , which principality collapses to a single generator.
The extended Euclidean algorithm computes the coefficients constructively, which is what makes modular inverses computable: is the inverse of modulo exactly when . That underlies RSA key generation, the Chinese remainder theorem, and continued-fraction convergents.
Stated for integers by Bachet de Méziriac in 1624 and extended to polynomials by Bézout.
Formalization note. The ambient ring is a CommRing that is an IsDomain,
IsPrincipalIdealRing and GCDMonoid, so gcd is a chosen representative rather than an
equivalence class. The result is Mathlib's exists_gcd_eq_mul_add_mul.
import Mathlib
namespace FamousTheorems
universe u v
open Filter Set Topology DirectSum
theorem bezout_identity {R : Type*} [CommRing R] [IsDomain R] [IsPrincipalIdealRing R]
[GCDMonoid R] (a b : R) : ∃ x y, gcd a b = a * x + b * y := by sorry
end FamousTheorems