Bézout's Identity
Bézout's Identity states that if and are nonzero integers and , then there exist integers and such that . In other words, there exists a linear combination of and equal to .
Furthermore, is the smallest positive integer that can be expressed in this form, i.e. . In particular, if and are relatively prime then there are integers and for which .
Proof
Let , , and notice that .
Since , . So is smallest positive for which . Now if for all distinct satisfying we have , then, by the Pigeonhole Principle, we can express every residue of as a multiple of . In particular, there is some positive for which . Assume for contradiction that , and WLOG let . Then, , and so as we saw above this means but this is impossible since . Thus there exists an such that .
Therefore , and so there exists an integer such that , and so . Now multiplying through by gives, , or .
Thus there does exist integers and such that .
Now to prove is minimum, consider any positive integer . As we get , and as and are both positive integers this gives . So is indeed the minimum.
Generalization/Extension of Bézout's Identity
Let be positive integers. Then there exists integers such that Also, is the least positive integer satisfying this property.
Proof
Consider the set . Obviously, . Thus, because all the elements of are positive, by the Well Ordering Principle, there exists a minimal element . So
if and then But by the Division Algorithm:
But so this would imply that which contradicts the assumption that is the minimal element in . Thus, hence, . But this would imply that for because . Now, because for we have that . But then we also have that . Thus, we have that