# 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 x_{0} and y_{0} such that:

d=ax_{0}+by_{0}

**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=ax_{0}+by_{0}, we substitute a=dq+r into the equation:

r = a−dq = a−(ax_{0}+by_{0})q = a(1−x_{0}q)+b(−y_{0}q)

So, r=a(1−x_{0}q)+b(−y _{0}q), 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 x_{0} and y_{0} such that:

gcd(a,b)=ax_{0}+by_{0}

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.