Proof:Bézout coefficients exist

From CS2800 wiki
For all [math]a, b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], there exists [math]s, t \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] such that [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) = sa + tb [/math].

[math]s [/math] and [math]t [/math] satisfying this equation are called Bézout coefficients of [math]a [/math] and [math]b [/math].

We will do this proof by induction. Since the inductive principle used to define [math]\href{/cs2800/wiki/index.php/Gcd}{gcd} [/math] uses strong induction on the second argument, we will use the same inductive principle for the proof. Let [math]\href{/cs2800/wiki/index.php?title=P&action=edit&redlink=1}{P}(b) [/math] be the statement "for all [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], there exists [math]s, t \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] such that [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) = sa + tb [/math]." We will prove [math]P(0) [/math] and [math]P(b) [/math] assuming [math]\href{/cs2800/wiki/index.php?title=P&action=edit&redlink=1}{P}(k) [/math] for all [math]k \lt b [/math].

To see [math]\href{/cs2800/wiki/index.php?title=P&action=edit&redlink=1}{P}(0) [/math], we have [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,0) = a = 1 \cdot a + 0 \cdot 0 [/math]. Thus choosing [math]s = 1 [/math] and [math]t = 0 [/math] gives the result we want.

Note that we could choose different values for [math]t [/math]; this shows that the Bézout coefficients are not necessarily unique.

Now, choose an arbitrary [math]b [/math]; we will show [math]P(b) [/math] assuming [math]\href{/cs2800/wiki/index.php?title=P&action=edit&redlink=1}{P}(k) [/math] for all [math]k \lt b [/math]. Let [math]g := \href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) = \href{/cs2800/wiki/index.php/Gcd}{gcd}(b,r) [/math]; we want to give a specific value of [math]s [/math] and [math]t [/math] such that [math]g = sa + tb [/math].

Note that since [math]r = \href{/cs2800/wiki/index.php?title=Rem(a,b)&action=edit&redlink=1}{rem(a,b)} [/math] we know [math]r \lt b [/math], so we have assumed [math]P(r) [/math]. This says that for any [math]a' [/math], there exists values [math]s' [/math] and [math]t' [/math] such that [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a',r) = s'a' + t'r [/math]. In particular, for [math]a' := b [/math] we have [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(b,r) = s'b + t'r [/math] for some [math]s' [/math] and [math]t' [/math].

We compute:

[math]\begin{align*} \href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) &= \href{/cs2800/wiki/index.php/Gcd}{gcd}(b,r) && \href{/cs2800/wiki/index.php/Gcd}{\text{by definition}} \\ &= s'b + t'r && \text{by }\href{/cs2800/wiki/index.php?title=P&action=edit&redlink=1}{P}(r) \\ &= s'b + t'(a - qb) && \text{since }\href{/cs2800/wiki/index.php/Remainder}{a = qb+r} \\ &= t'a + (s' - t'q)b && \text{algebra} \\ &= sa + tb \end{align*} [/math]

if we let [math]s := t' [/math] and [math]t := s' - t'q [/math].