Proof:Gcd(a,b) is greater than all other common divisors of a and b

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 [math]P(0) [/math], assume and . We want to show that [math]c [/math] divides . Well, we have assumed this, so there's nothing to show!

Now, choose an arbitrary [math]b [/math]; we will show [math]P(b) [/math] assuming for all [math]k \lt b [/math]. Assume that and . Let ; we want to show that .

Note that since we know [math]r \lt b [/math], so we have assumed [math]P(r) [/math]. We could apply [math]P(r) [/math] 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 [math]sc = a [/math]
so there exists with [math]tc = b [/math]
Since we know that [math]a = qb + r [/math] for some [math]q [/math].
We want to show , i.e. that there exists with [math]r = kc [/math].

Putting the things we know together, we have

So choosing gives as required.