It Goes On And On

A more precise proof, by induction: Let $f(a,b)$ be the output for any given integers $a \geq 1$ and $b \geq 0$ .

Basis step . If $a + b = 1$ , then clearly the algorithm produces $f(1,0) = 1 = \gcd(1,0)$ .

Induction step . Suppose that for all situations with $a + b < n$ we have that $f(a,b) = \gcd(a,b)$ ; here $n \geq 2$ . We will prove that this is then also true for $a + b = n$ .

So let the input be such that $a + b = n$ . There are three cases to consider.

• $a = n$ and $b = 0$ . The algorithm immediately gives $f(n,0) = n = \gcd(n,0)$ .

• $a < b$ . The algorithm prescribes $f(a,b) = f(a, b-a)$ . Since $a + (b-a) = b < n$ (we assumed $a \geq 1$ ), we use the induction step to conclude $f(a,b) = f(a,b-a) = \gcd(a,b-a) = \gcd(a,b),$ the last equality being a key property of the gcd function.

• $a \geq b$ . Now we must evaluate $f(a, b) = f(b, a-b)$ . Similar to the previous step, $b + (a-b) = a < n$ (we ruled out $b > 0$ ), and using the induction assumption we get $f(a,b) = f(b,a-b) = \gcd(b,a-b) = \gcd(a,b).$

Conclusion . Thus we conclude that $f(a,b) = \gcd(a,b)$ for all values of $n = a + b$ , which means that it is true for all pairs $(a,b)$ .

Let $z(a,b)$ be the number of steps needed to calculate $f(a,b)$ . It is easy to prove by induction that $z(a,b) \geq a+b+1$ using induction on $n = a+b$ .

In my original solution I swapped $a$ and $b$ . It should be better now. I also gave a more precise proof of the finitude of the process.

Perhaps this helps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(79,23)
(23,56)
(23,33)
(23,10)
(10,13)
(10,3)
(3,7)
(3,4)
(3,1)
(1,2)
(1,1)
(1,0)
Output: 1

This was produced with the following Java code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int a = 79, b = 23;

while (true) {
    System.out.print('(');
    System.out.print(a);
    System.out.print(',');
    System.out.print(b);
    System.out.println(')');

    if (b == 0) {
        System.out.print("Output: ");
        System.out.println(a); break;
    }
    else {
        if (a >= b) { int t = a; a = b; b = t; }
        b -= a;
    }
}