# Proof:Bézout coefficients exist

For all , there exists such that .

and satisfying this equation are called Bézout coefficients of and .

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 and gives the result we want.

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

Now, choose an arbitrary ; we will show assuming for all . Let ; we want to give a specific value of and such that .

Note that since we know , so we have assumed . This says that for any , there exists values and such that . In particular, for we have for some and .

We compute:

if we let and .