Bézout's Identity

Number Theory · Axiom Academy

A fundamental theorem about linear combinations of integers and the greatest common divisor 1. Statement of Bézout's Identity In other words, the greatest common divisor can always be written as a linear combination of the two numbers. The coefficients x and y are called Bézout coefficients . We need to find x and y such that 30 x + 21 y = 3 One solution: x = -2 and y = 3, since 30(-2) + 21(3) = -60 + 63 = 3 2. The Extended Euclidean Algorithm The proof of Bézout's Identity is constructive—we can actually compute the coefficients using the Extended Euclidean Algorithm . Run the standard Euclidean algorithm to find gcd( a , b ) Work backwards through the divisions to express the gcd as a linear combination At each step, substitute the remainder from the previous step So gcd(252, 105) = 21. Now work backwards: Now we prove that Bézout's Identity always holds, and that d is the smallest positive linear combination. Define the set S: Let S = ax + by > 0 : x , y ∈ ℤ . This is the set of all positive linear combinations of a and b . S is non-empty: Since either a or b is non-zero, we can write | a | or | b | as a positive linear combination, so S ≠ ∅. Let d be the minimum: By the Well-Ordering Principle, S has a smallest element. Call it d = ax₀ + by₀ for some integers x₀ , y₀ . Show d divides a: Divide a by d : a = dq + r where 0 ≤ r d . Then: This is a linear combination of a and b . If r > 0, then r ∈ S , contradicting minimality of d . So r = 0, hence d | a .

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