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$
No comments:
Post a Comment