Bézout’s Identity definition
Bézout’s identity says the greatest common divisor of two integers can be written as an integer linear combination of them.
Bézout’s Identity in a picture
How it works
If a and b are not both zero, some integers x and y satisfy ax + by = gcd(a, b). Work backward through the Euclidean algorithm to find such coefficients. When a and b are coprime, the right side is 1. This gives modular inverses and helps solve integer equations.
Worked examples
Write gcd(12, 8) as a combination.
4 = 12 − 8.
Write gcd(7, 3) as a combination.
1 = 7 − 2 × 3.
Use 1 = 7 − 2 × 3 to find an inverse of 3 modulo 7.
−2 ≡ 5 (mod 7), so 5 is an inverse.
Common mistake
The coefficients can be negative and need not be unique. Check the final combination equals the gcd.
Quick check
What type of coefficients does the identity use?
Show answer
Integers.
What is the right side for coprime inputs?
Show answer
1.
What algorithm can produce the coefficients?
Show answer
The extended Euclidean algorithm.
Sources
Flashcard
Bézout’s Identity
Reveal the definition
Bézout’s identity says the greatest common divisor of two integers can be written as an integer linear combination of them.
Effortless Math. “Bézout’s Identity.” Math Dictionary.
