Proof:Gcd(a,b) is a common divisor of a and b
From CS2800 wiki
Euclid's GCD algorithm is the function which is given as follows: , and for , where .
The algorithm can be extended to operate on negative integers by simply taking the gcd of the absolute values of its arguments.
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 .
Let's take stock of where we are:
- Since we have for some .
- We also have for some since .
- We also know for some since .
- We want to show that there exists with .
Combining these equations, we have
Thus, choosing shows as required.