Consider the set of all linear combinations of and , that is,
and suppose is the smallest positive integer in this set. For example, if and , then you can check that, for example, , and , and are all in this set, as is, for example, , but the smallest positive integer you can get is . We will prove that in fact, is the greatest common divisor of and .
Consider dividing by . This will result in some remainder such that . I claim the remainder is also of the form for some integers and : note that is of this form, and is of this form by definition, and we get the remainder by subtracting some number of copies of from . Subtracting two numbers of the form works by subtracting coefficients, yielding another number of the same form again. But is supposed to be the smallest positive number of this form, and is less than —which means has to be zero, that is, evenly divides . The same argument shows that evenly divides as well. So is a common divisor of and .
To see that is the greatest common divisor, suppose also divides and . Then since , we can see that must divide as well—so it must be less than or equal to .
Voila! This proof doesn’t show us how to actually compute some appropriate and given and —that can be done using the extended Euclidean algorithm; perhaps I’ll write about that some other time. But this proof will do for today.
For the remainder of the month, as suggested by commented janhrcek, we’ll prove the thing I hinted at in an earlier post: namely, that the order of any group element is always a divisor of the order of the group. This is a really cool proof that hints at some much deeper group theory.