I know that succesive division approach is better in efficiency terms, but I am trying to prove that the substraction approach is also correct for any pair of integers and it will complete always in a finite number of steps.
For me it was easier to prove the division approach, but I can’t understand why it also works with substraction.
On
I will outline, but not do, a sufficient proof.
First, use double strong induction to prove:
If
i <= j, the subtraction procedure for both(i, j)and(j, i)will terminate in a finite number of steps.
The difference between weak and strong induction is explained here.
By double strong induction I mean do a proof by strong induction on i. The induction step will require a proof by strong induction on j.
Next, prove this. Prove that every step of the subtraction algorithm always results in a pair of the form (a*i + b*j, c*i + d*j) and therefore any common divisor of i, j divides it. (Proceed by induction on the number of steps.) From that, prove that every common divisor divides the answer found by the subtraction algorithm.
Now do the reverse. Prove the following. If the reduction from (i, j) down to (x, x) (with x not 0) can be achieved by the subtraction algorithm in n steps, then both i and j are multiples of x. That proves that the result of the subtraction algorithm is a common divisor.
The common divisor that all other divisors divide must be the greatest common divisor.
(Your teacher would probably accept a shorter proof using other results already shown in class. But I don't know what you've already been presented with.)
The euclidean algorithm is based on the division algorithm of integers. The wikipedia page states that division with remainder is equivalent to repeated subtraction, which should explain your question.