A few days ago we made use of *Bézout’s Identity*, which states that if and have a greatest common divisor , then there exist integers and such that . For completeness, let’s prove it.

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.

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

When showing that is a common divisor, you state “…that is, evenly divides .” The next sentence states “…shows that evenly divided as well.” Shouldn’t the second be ?

Yup, good catch, thanks! Fixed now.