# SP20:Lecture 16 Bézout coefficients

In this lecture, we did 3 similar proofs: that the GCD is a common divisor, that it is the greatest common divisor, and that the Bézout coefficients exist.

# Greatest common divisor

An important technical tool for our study of number theory is the greatest common divisor of two numbers. Here we present an efficient algorithm for computing it:

Definition: gcd
Euclid's GCD algorithm is the function which is given as follows: , and for , where .

This function is a good inductively defined function because by definition, , so the second argument is decreasing in the inductive definition.

The algorithm can be extended to operate on negative integers by simply taking the gcd of the absolute values of its arguments.

In order to justify calling the "greatest common divisor", we should check that gcd(a,b) is a common divisor of a and b and gcd(a,b) is greater than all other common divisors of a and b.

For all , if and , then .

## Choosing an inductive priniple

We will prove both of these claims by induction, but we have a choice to make: should we use induction on or on (or both?).

Often, when proving things about an inductively defined function, it is useful to use the same inductive principle for the proof as was used for the definition. For example, we argued that the function is well-defined because it's second argument is decreasing (that is, while defining , we could assume that was already defined, since . This is a form of strong induction argument on . Therefore, a good heuristic for proving things about is to do induction on the second argument. That is, to prove "for all , some fact involving ", it makes sense to define as "for all , the fact involving ", and then use strong induction to prove for all .

The reason for this is that in the inductive step, you are likely to plug in the definition, and you would then like to apply the inductive hypothesis to reason about the expression you derive. If the inductive principle used in your proof matches the inductive principle used in your definition, you will be able to do this.

## gcd is a common divisor

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 , and ". We will prove and assuming for all .

To see , we want to show that and . Note that by definition, . because , and because .

Now, to see , assume for all . To save some writing, let's define , by definition, we have (for simplicity, let's call this number ); thus we want to show that and .

Now, since , we know . Thus we can apply (with plugged in for ), to conclude that and . This gives us one of the two things we need to prove, so all that's left is to show that .

Let's take stock of where we are:

Combining these equations, we have

Thus, choosing shows as required.

## gcd is the greatest common divisor

For all , if and , then .

In fact, we will prove the following claim, which is stronger:

For all , if and , then .

This claim is stronger because if c ❘ g then c ≤ g.

Proof: of stronger claim
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 , if and then ." We will prove and assuming for all .

To see , assume and . We want to show that divides . Well, we have assumed this, so there's nothing to show!

Now, choose an arbitrary ; we will show assuming for all . Assume that and . Let ; we want to show that .

Note that since we know , so we have assumed . We could apply to show that if we could show that and . And we're already halfway there: we've already assumed . Thus we just need to show that .

Let's take stock of where we are:

• so there exists with
• so there exists with
• Since we know that for some .
• We want to show , i.e. that there exists with .

Putting the things we know together, we have

So choosing gives as required.

# Bézout coefficients

We used the last part of the lecture to prove a useful fact:

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 .