Bézout’s Lemma §

Bézout’s Lemma is a fundamental theorem in number theory and algebra. It states:

For any integers $a$ and $b$, if $d$ is their greatest common divisor (GCD), then there exist integers $x$ and $y$ such that:

$ax+by=d$

In other words, the GCD of two integers can always be expressed as a linear combination of those integers.

Proof: §

1. Consider the set $S$ of all positive integers of the form $ax+by$, where $x$ and $y$ are integers. Since $a$ and $b$ are not both zero, the set $S$ is non-empty.

2. Let $d$ be the smallest positive integer in $S$. By the division algorithm, for any integer $c$ in $S$, we can write $c=dq+r$ where $0\le r<d$.

3. Now, $r=c-dq=(ax+by)-d(a{x}^{\prime }+b{y}^{\prime })=a(x-x^{\prime }q)+b(y-y^{\prime }q)$. Since $x-x^{\prime }q$ and $y-y^{\prime }q$ are integers, $r$ is also of the form $a{x}^{\prime \prime }+b{y}^{\prime \prime }$. Thus, $r$ is in $S$.

4. But, $r<d$ and $d$ is the smallest positive integer in $S$. So, the only possibility is $r=0$. This means every integer in $S$ is a multiple of $d$.

5. Since $a$ and $b$ are in $S$, $d$ divides both $a$ and $b$. Thus, $d$ is a common divisor of $a$ and $b$.

6. If there’s any common divisor $c$ of $a$ and $b$, then $c$ divides any integer of the form $ax+by$. In particular, $c$ divides $d$. Thus, $d$ is the greatest common divisor of $a$ and $b$.

7. Therefore, the GCD of $a$ and $b$ can be expressed as a linear combination of $a$ and $b$.

Consequence of Bézout’s Lemma §

$$\left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right)=1$$

This is just taken when we take a linear combination in the form of the lemma, then dividing everything through by the greatest common divisor - of course this is equal, but it also creates a coprime pair of integers.

$ax+by=(a,b)$, for some $x,yϵz$, $⟹\frac{ax}{(a,b,)}+\frac{by}{(a,b,)}=1$ $ax+by=1⟺(a,b)=1$ for some $x,yϵz$, $\therefore \text{ the lemma is proven.}■$

Applications: §

Bézout’s Lemma is foundational in many areas of mathematics, especially in number theory. It’s used in the proof of the Fundamental Theorem of Arithmetic and in the solution of Diophantine equations. Additionally, it plays a crucial role in the theory of modular arithmetic and the RSA encryption algorithm in cryptography.

---

This note provides a comprehensive overview of Bézout’s Lemma, its proof, and its significance in various mathematical applications.