_Posted on April 12, 2024_ #TODO Make this interesting somehow. ##### Introduction The statement of Bézout's Lemma is the following: > [!theorem] **(Bézout's Lemma):** _Let $a$ and $b$ be integers. The greatest common divisor is the smallest positive linear combination of $a$ and $b$._ ##### Prerequisites First, I define the greatest common divisor between two integers $a$ and $b$: > [!definition] For integers $a$ and $b$, $\text{GCD}(a,b) = d$ if and only if > 1. $d \mid a$ and $d \mid b$ > 2. If $c \mid a$ and $c \mid b$, then $c \mid d$. Note that there is an alternative definition of the greatest common divisor, in terms of [[Euclid's Division Lemma]], given in my post on [[The Euclidean Algorithm]]. In the proof of Bézout's Lemma given below, we show that the set of linear combinations of two integers is a principal ideal of the ring $\mathbb{Z}$. What this means formally is introduced using the following lemma, without relying on any understanding of ideals or even rings. > [!theorem] **Principal Ideal Lemma:** _$S$ = $n\mathbb{Z}$ for some $n \in \mathbb{Z^{\geq0}}$ if and only if $a, b \in S \implies a - b \in S$ and $t \in \mathbb{Z} \text{, } a \in S \implies ta \in S$._ Proof: Let $S = n\mathbb{Z}$ for some $n \in \mathbb{Z}$. Suppose that $a,b \in S$. We have $n \mid a$ and $n \mid b$. Thus, $n \mid a - b$, which implies that $a - b \in S$. Now, suppose that $t \in \mathbb{Z}$ and $a \in S$. Since $n \mid a$, we have $nk = a$ for some integer $k$. This implies that $ta = tnk = n(tk)$ and so $n \mid ta$, which implies that $ta \in S$. Now we prove the converse. If $S$ only contains $0$, then $S = 0\mathbb{Z}$. Otherwise, $S$ contains some positive integer $t$. That is, if $t < 0$ then $S$ contains $(-1)t = -1 > 0$. By the [[Euclid's Division Lemma#^ee5ece|Well Ordering Principle]], there is a least such positive integer in $S$. Let $n$ be this integer. Now, we will show that $S = n\mathbb{Z}$ by demonstrating that for all $a\in S\text{, }n \mid a$. Suppose that $t \in S$. By [[Euclid's Division Lemma|Euclid's division lemma]], we have $t = nq + r$ with $0\leq r < n$. This implies that $r = t - nq \in S$ which contradicts $n$ being the smallest positive integer in $S$ when $r \neq 0$. Thus $r = 0$ and $t = nq$, implying that $n \mid t$ $\blacksquare$ ##### Proof Proof of Bézout's Lemma: Let $S = \{ma + nb : m,n\in \mathbb{Z}\}$. Notice that for two elements $t,l$ of $S$, $t - l \in S$, and that for $t \in \mathbb{Z}$ and $a \in S$, $ta \in S$. Thus, $S = d\mathbb{Z}$ where $d$ is the least positive integer in $S$ by the Principal Ideal Lemma. Now, we need to show that $d = \text{GCD}(a,b)$. Since $a,b \in S$, $d$ divides both $a$ and $b$. Now, suppose we have some $c$ such that $c \mid a$ and $c \mid b$. Then $d = ctm + cln = c(tm + ln)$ so that $c \mid d$. Thus by the definition of greatest common divisor, $d = \text{GCD}(a,b)$ $\blacksquare$ ##### A useful corollary > [!theorem] _If integers $a$ and $b$ are co-prime, the set of linear combinations of $a$ and $b$ is $\mathbb{Z}$._ Proof: By Bézout's Lemma, the smallest positive linear combination of $a$ and $b$ is $\text{GCD}(a,b)$. However, by the definition of co-prime, $\text{GCD}(a,b) = 1$. Further, by The Principal Ideal Lemma, the set of linear combinations of $a$ and $b$ is $1\mathbb{Z} = \mathbb{Z}$ $\blacksquare$ --- The ideas of the main proof were adapted from _Introduction to the theory of numbers_ by Harold N. Shapiro. #TODO There is apparently an algorithm to find m and n. An example is given on page 12 of Allufi notes from the underground.