Bezouts Identity
By Sudheer S
Introduction
In this series of articles on number theory, today we talk about the Bézout’s Identity.
Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. The integers of the form az + bt are exactly the multiples of d.
The integers x and y are called Bézout coefficients for (a, b); they are not unique
Existence Proof of Bézout’s Identity
The proof of Bézout’s Identity typically involves the Euclidean algorithm, which is used to find the greatest common divisor of two integers.
Step 1: Define the Set S
Consider the set S defined as: S = {ax+by∣x, y∈Z, ax+by>0}
S is the set of all positive integers that can be expressed as a linear combination of a and b.
where x and y are any integers, elements of Z and
the expression ax+by must be greater than zero (positive).
Step 2: Show that S is non-empty.
Since a and b are nonzero, there exist integers x and y such that ax+by is positive. Therefore, S is a non-empty set of positive integers.
Step 3: Consider the Smallest Element of S
By the well-ordering principle (a fundamental property of the integers), any non-empty set of positive integers has a smallest element.
This is a formal statement. Intuitively, it makes sense to say that any non-empty set of positive integers has a smallest element. In other words, one of the elements of the non-empty set of positive integers will be the smallest.
Let d be the smallest element in S.
So, there exist integers x0 and y0 such that:
d=ax0+by0
Step 4: Show that d divides both a and b
Now, we need to show that d=gcd(a,b). To do this, we’ll show that d divides both a and b.
Using the division algorithm, divide a by d to get:
a = dq + r
where q is the quotient and r is the remainder with 0≤r<d.
When you divide a by d, ie a/d, you either get the remainder r = 0, or you you get the remainder r > 0.
And r is less than d.
Since d=ax0+by0, we substitute a=dq+r into the equation:
r = a−dq = a−(ax0+by0)q = a(1−x0q)+b(−y0q)
So, r=a(1−x0q)+b(−y 0q), which implies r can also be written as a linear combination of a and b.
If r>0, then r would be an element of S that is smaller than d, which contradicts the minimality of d. Therefore, r=0 and d divides a. Similarly, d also divides b.
Step 5: Conclude d=gcd(a,b)
Since d divides both a and b, and d is a linear combination of a and b, d must be the greatest common divisor of a and b.
Thus, we have shown that d=gcd(a,b), and there exist integers x0 and y0 such that:
gcd(a,b)=ax0+by0
This completes the existence proof of Bézout’s Identity.
Food For Thought
How do you compute the values of x and y given a and b has the form ax+by=gcd(a,b)?
We already know how to compute the GCD of the integers a and b using the Euclidean algorithm. The missing parts are x and y. That’s the topic for our next blog post, ie, the extended Euclidean algorithm.