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

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,

$a{x}_0+b{y}_0=d$

Or, $\frac{d(a{x}_0+b{y}_0)}{d}=d$

Or, $\frac{da{x}_0+db{y}_0}{d}=d$

Or, $\frac{da{x}_0-kba+kba+db{y}_0}{d}=d$

Or, $a{x}_0-ak\frac{b}{d}+b{y}_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})=a{x}_k+b{y}_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\ne 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=\lfloor \frac{a}{d}\rfloor$, $r=a-d\lfloor \frac{a}{d}\rfloor$ and $0\le 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\le 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$ $⟹c\le 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]