The GCD and linear combinations
July 10th, 2009 at 7:49 amA linear combination of a and b is some integer of the form 
, where 
.
There’s a very interesting theorem that gives a useful connection between linear combinations and the GCD of a and b, called Bézout’s identity:
Bézout’s identity: 
(the GCD of a and b) is the smallest positive linear combination of non-zero a and b.
Both Bézout’s identity and its corollary I show below are very useful tools in elementary number theory, being used for the proofs of many of the most fundamental theorems. Let’s see why it’s true.
(I) Intuition: First I’d like to explain this (surprising at first sight) theorem intuitively. By defintion, any common divisor of a and b will divide for all . In particular, also divides any .
Now, assume we’ve found some small 
which isn’t the GCD. But we’ve just said that divides all linear combinations, so it also divides x. Therefore, x can not be smaller than the GCD. In other words, the smallest positive linear combination can only be itself.
Corollary: An integer is a linear combination of a and b IFF it is a multiple of their GCD.
To prove Bézout’s identity more formally, and along the way to see why the corollary is also true, let’s first prove the following:
(III) Let I be a nonempty set of integers that is closed under addition and subtraction, and contains at least one non-zero integer. Then there exists a smallest positive element 
, and I consists of all multiples of b (
).
Proof: I contains at least one non-zero integer. Then it definitely contains at least one positive integer, because it is closed under addition and subtraction. Assume we have 
for some 
. Therefore 
and then also 
. Thus we have positive integers in I. According to the well-ordering principle, I has a smallest positive element which we’ll call b.
Now we’ll want to show that . As usual, to prove equalities of sets, it will be shown that they contain one another.
is obvious - since I contains b and is closed under addition and subtraction, it contains all the multiples of b.
To prove 
we’ll demonstrate that any element 
is a multiple of b. Using the division algorithm we write 
for some integers q and 0 <= r < b. But this means that 
(because I contains bq and c and is closed under subtraction and addition). However, recall that b was chosen to be the smallest positive element of I, so r must be equal to 0. Therefore c is a multiple of b, and we have shown that . Q.E.D.
Now back to Bézout’s identity. We’ll define:
This I is obviously non-empty and is closed under addition and subtraction (by its definition as a linear combination). Note, in particular, that it also contains a and b. By (III), I consists of all multiples of its smallest positive element, which we’ll call d here.
To show that 
we have to show that d|a, d|b and if c|a and c|b then c|d. First, by definition d is a divisor of any element in I, so it also divides a and b. If c|a and c|b, say a=cq and b=cp, then:
So d|c, which completes our proof that d=(a,b). Q.E.D.
Regarding the corollary, it stems trivially from the definition of I and the proof above.
Related posts: