In the first post on greatest common divisor we saw that is the largest positive integer such that and . There are in fact multiple ways of characterizing the GCD of two integers. In this post I will present another way of looking at GCD. This characterization says that is the least positive integer that is a ** linear combination** of and , i.e. a number for . The proof uses the

**which says that every non-empty subset of positive integers has a least element (this can be taken as an axiom of the integers). The proof will also use the division algorithm and facts about divisibility. Here is the theorem:**

*well-ordering property***Theorem:** The greatest common divisor of the integers and , not both zero, is the least positive integer that is a linear combination of and .

**Proof:** Suppose is the least positive integer such that for some integers . We know that the set of the set of positive integers is nonempty because we may take either or , so our exists by the well-ordering property. By the division algorithm we have that for some integers where , and so

So is a linear combination of and but . If this would contradict our assumption that is the least such positive integer, so it must be that case that . So in fact , so . Similarly we may show that . This shows is a common divisor of and . It remains to show it is the greatest common divisor. Suppose and and . Then so , but this implies a contradiction. So is indeed the greatest common divisor.

In sage the `xgcd(a,b)`

command gives a tuple with three entries: `(d,m,n)`

where as in the proof above.