Bézout's Identity
What You'll Learn
You'll discover that the greatest common divisor (GCD) of two integers can always be expressed as an integer combination of those two numbers.
The Core Idea
Bézout's Identity states: For any two integers a and b (not both zero), there exist integers x and y such that:
ax + by = gcd(a, b)
This is a powerful statement. It tells us that the GCD isn't just some abstract "largest common divisor"—it's something we can actually construct using the two original numbers through addition, subtraction, and multiplication by integers.
Why This Matters
The Extended Euclidean Algorithm (which you just learned) is the practical tool that finds these coefficients x and y. Bézout's Identity is the theoretical guarantee that such coefficients always exist.
A Concrete Example
Consider a = 35 and b = 15. We know gcd(35, 15) = 5.
Bézout's Identity promises integers x and y where: 35x + 15y = 5
One solution: x = 1 and y = −2
- Check: 35(1) + 15(−2) = 35 − 30 = 5 ✓
An Analogy
Think of a and b as two different-sized measuring cups. Bézout's Identity says that by filling and emptying these cups (adding and subtracting multiples), you can always measure out exactly one unit of their GCD—no more, no less.
Important Note
The coefficients x and y are not unique. There are infinitely many pairs that work! But at least one pair always exists.
Key Takeaway: Bézout's Identity guarantees that gcd(a, b) can always be written as an integer linear combination ax + by, and the Extended Euclidean Algorithm finds the coefficients x and y.