# Timeless Theorems of Mathematics/Bézout's Identity

!Étienne Bézout *(31 March 1730 -- 27 September
1783)*")
**Bézout\'s Identity** is a theorem of Number Theory and Algebra, which
is named after the French mathematician, Étienne Bézout *(31 March 1730
-- 27 September 1783)*. The theorem states that the greatest common
divisor, $$ of the integers, $a$ and $b$ can be written in the form,
$ax + by = d,$ where $x$ and $y$ are integers. Here, $x$ and $y$ are
called Bézout coefficients for $(a, b)$.

## Computing the pairs, $(x, y)$

There are infinite number of pairs of $(x, y)$ which satisfies the
equation $ax + by = d,$. A general formula can be developed to compute
pairs as much as you want. To do that, first of all, it\'s required to
calculate one pair of $(x, y)$. One simple way to calculate a pair is
using the **extended Euclidean algorithm**.

### General Formula for Computing

Once you have one pair $(x_0, y_0),$ you can apply the formula,
$(x_k, y_k) = (x_0 - k\frac{b}{d}, y_0 + k\frac{a}{d})$where $k\in \Z$,
that means $k$ is an integer.

**Proof:** As $(x, y)=(x_0, y_0)$ satisfies the equation $ax + by = d,$
then,

$ax_0 + by_0 = d$

Or, $\frac {d(ax_0 + by_0)}{d} = d$

Or, $\frac {dax_0 + dby_0}{d} = d$

Or, $\frac {dax_0 -kba + kba + dby_0}{d} = d$

Or, $ax_0 - ak\frac{b}{d} + by_0 + bk\frac{a}{d} = d$

Or, $a(x_0 - k\frac{b}{d}) + b(y_0 + k\frac{a}{d}) = d$

Or, $a(x_0 - k\frac{b}{d}) + b(y_0 + k\frac{a}{d}) = ax_k + by_k$

Therefore, the coefficients of $a$ are equal and the coefficients of $b$
are also equal, $(x_k, y_k) = (x_0 - k\frac{b}{d}, y_0 + k\frac{a}{d})$

*\[Note: The formula only works when $d \neq 0$. Also, as $x\in\Z$, then
$k\in\Z$.\]*

**Example:** The greatest common divisor of $a = 8$ and $b = 12$ is
$\gcd(8, 12) = 4.$ According to the identity, there exists integers $x$
and $y$, so that $8x + 12y = 4$ $\Rightarrow 2x + 3y = 1$. If you try to
solve the equation, you may soon come up with a pair of solutions like
$(x_0, y_0) = (-1, 1)$. So,
$(x_k, y_k) = (-(1 + k\frac{b}{d}), 1 + k\frac{a}{d})$. By using this
formula, you may find pairs as much as you want.

## Proof

Assume $S = \{ax+by:x,y\in\Z \text{ and } ax+by>0\}$ where $a$ and $b$
are non zero integers. The set is not an empty set as it contains either
$a$ or $-a$ when $x = \pm 1$ and $y=0$. Since $S$ is not an empty set,
by the well-ordering principle, the set has a minimum element
$d = as + bt$.

The Euclidean division for $\frac {a}{d}$ may be written as
$a = dq + r$, where $q=\left\lfloor {\frac{a}{d}} \right\rfloor$,
$r = a - d \left\lfloor {\frac{a}{d}} \right\rfloor$ and $0 \leq r <d$.

Here, $r = a - dq$ $= a - q(as + bt)$ $= a - qas + qbt$
$= a(1 - qs) + b(qt)$

Thus, $r$ is in the form $ax+by$, and hence $r\in S\cup\{0\}$. But,
$0\leq r<d$ and $d$ is the smallest positive integer in $S$. So, $r$
must be $0$. Thus, $d$ is a divisor of $a$. $q = \frac {a}{d} > 0$ as
the remainder is zero and a is a non zero integer. Similarly, $d$ is
also a divisor of $b$. Therefore, $d$ is a common divisor of $a$ and
$b$.

Assume $c$ as any common divisor of $a$ and $b$; $a = cu$, $b = cv$.
Again, $d = as+bt$ $= cus + cvt$ $= c(us + vt)$

Thus, $c$ is a divisor of d. Since $d>0$ $\implies c\leq d$. Therefore,
any common divisor of $a$ and $b$ is less than or equals to $d$.

$\therefore d$ is the same as $gcd(a, b)$ and $d$ can be expressed as
$ax + by = d$. ***\[Proved\]***

