Proof:Bézout coefficients exist

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

Proof:

We will do this proof by induction. Since the inductive principle used to define uses strong induction on the second argument, we will use the same inductive principle for the proof. Let be the statement "for all , there exists such that ." We will prove and assuming for all .

To see , we have . 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 for all [math]k \lt b [/math]. Let ; 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 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 . In particular, for [math]a' := b [/math] we have for some [math]s' [/math] and [math]t' [/math].

We compute:

if we let and .