Can you express the greatest common divisor of two numbers as a linear combination?
In short: Bézout's identity reveals that the greatest common divisor of any two integers can always be written as a linear combination of those same numbers. This fundamental theorem, named after Étienne Bézout, serves as a cornerstone for various proofs in elementary number theory, including Euclid's lemma and the Chinese remainder theorem.
At its core, Bézout's identity states that for any two integers, there exist coefficients that allow you to express their greatest common divisor as a linear combination. While these coefficients are not unique, the extended Euclidean algorithm provides a reliable method to compute them. When two integers are not both zero, there are infinitely many pairs of coefficients that satisfy the identity, but exactly two of these are considered minimal based on their absolute values relative to the original numbers.
The proof of this identity relies on the well-ordering principle. By considering the set of all positive integers that can be formed as a linear combination of two given integers, one can identify a smallest element. Through Euclidean division, it can be shown that this smallest element must be the greatest common divisor. This logic extends beyond simple integers; the identity holds within any principal ideal domain, making it a powerful tool across broader algebraic structures.
While the identity is robust for integers and univariate polynomials with coefficients in a field, it does not apply universally to all rings. For instance, if you work with polynomials that have integer coefficients, you may find that the greatest common divisor cannot be expressed as a linear combination using those same types of polynomials. For example, the greatest common divisor of two specific polynomials might be a simple variable, yet no combination of those polynomials with integer-coefficient factors can produce it.
Beyond two numbers, the identity generalizes to any number of integers. If you take the greatest common divisor of a set of integers, that value is the smallest positive integer that can be represented as a linear combination of the entire set. Every other number formed by such a combination is guaranteed to be a multiple of that divisor, reinforcing the identity's central role in understanding the structure of divisibility.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Bézout's identity
To cite this card, link to https://intellectplus.co.uk/app/science-b-zout-s-identity.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Number theory · More in Science · Latest · A–Z · All topics