Timeless Theorems of Mathematics/Bézout's Identity

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, ${\displaystyle }$ 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)$.

Étienne Bézout (31 March 1730 – 27 September 1783)

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 \mathbb {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 \mathbb {Z}$, then $k\in \mathbb {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 \mathbb {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]