Bezout's Identity

Theorem 3:  Bezout's Identity

Let $a$ and $b$ be nonzero integers with greatest common divisor $d$.  Then, there exists integers $x$ and $y$ such that $ax + by = d$.

Proof:

(1)  For integers $a,b$ let $S$ be a set that includes all $ax+by$ where $ax + by > 0$

(2)  The set is non-empty since it contains either $a$ or $-a$ where $y=0$ and $x=1$ or $x=-1$

(3)  By the Well-Ordering Principle, $S$ has a minimal element $as + bt$ and let $d = as+bt$

(4)  Using Euclid's Divsion Lemma, there exists $q_1, q_2, r_1, r_2$ such that:

• $a = q_1d + r_1$
• $b = q_2d + r_2$

(5)  It follows that:

• $r_1 = a - q_1d = a - q_1(as + bt) = a(1 - q_1s)  + b(-q_1t)$ which must equal $0$ since $r_1 < d$ but $d$ is the least element in $S$.  The same argument applies to $r_2$ so that $r_2 = 0$

(6)  Then, $d$ divides both $a$ and $b$.

(7)  Let $c$ be any common divisor of $a$ and $b$ such that $a =cu$ and $b = cv$

(8)  $d = as + bt = cus + cvt = c(us + vt)$ so that it follows that $c$ divides $d$ and further that $c \le d$