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.
This entry was posted in algebra, arithmetic, modular arithmetic, number theory and tagged , , , , , , , . Bookmark the permalink.

2 Responses to MaBloWriMo 24: Bezout’s identity

  1. Logan says:

    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?

Comments are closed.