MaBloWriMo 24: Bezout’s identity

A few days ago we made use of Bézout’s Identity, which states that if $a$ and $b$ have a greatest common divisor $d$ , then there exist integers $x$ and $y$ such that $ax + by = d$ . For completeness, let’s prove it.

Consider the set of all linear combinations of $a$ and $b$ , that is,

$\{ax + by \mid x, y \in \mathbb{Z} \}$ ,

and suppose $d = as + bt$ is the smallest positive integer in this set. For example, if $a = 10$ and $b = 6$ , then you can check that, for example, $16 = a + b$ , and $8 = 2a - 2b$ , and $4 = a - b$ are all in this set, as is, for example, $-4 = -a + b$ , but the smallest positive integer you can get is $2 = 2a - 3b$ . We will prove that in fact, $d$ is the greatest common divisor of $a$ and $b$ .

Consider dividing $a$ by $d$ . This will result in some remainder $r$ such that $0 \leq r < d$ . I claim the remainder is also of the form $ax + by$ for some integers $x$ and $y$ : note that $a = a1 + b0$ is of this form, and $d$ is of this form by definition, and we get the remainder by subtracting some number of copies of $d$ from $a$ . Subtracting two numbers of the form $ax + by$ works by subtracting coefficients, yielding another number of the same form again. But $d$ is supposed to be the smallest positive number of this form, and $r$ is less than $d$ —which means $r$ has to be zero, that is, $d$ evenly divides $a$ . The same argument shows that $d$ evenly divides $b$ as well. So $d$ is a common divisor of $a$ and $b$ .

To see that $d$ is the greatest common divisor, suppose $c$ also divides $a$ and $b$ . Then since $d = ax + by$ , we can see that $c$ must divide $d$ as well—so it must be less than or equal to $d$ .

Voila! This proof doesn’t show us how to actually compute some appropriate $x$ and $y$ given $a$ and $b$ —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

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

View all posts by Brent →

2 Responses to MaBloWriMo 24: Bezout’s identity

Logan says:

November 25, 2015 at 5:58 pm

When showing that $d$ is a common divisor, you state “…that is, $d$ evenly divides $a$ .” The next sentence states “…shows that $d$ evenly divided $a$ as well.” Shouldn’t the second be $b$ ?
- Brent says:
  
  November 25, 2015 at 11:15 pm
  
  Yup, good catch, thanks! Fixed now.

Comments are closed.