Question

Prove that Algorithm 3 for computing gcd (a,b) when a and b are positive integers with a < b is correct.

Short answer

The recursive algorithm is proved.

Step-by-step solution

Describe the Algorithm 3

This can be proved by Strong Induction.

Take a = 0.

The algorithm returns b, while gcd (a,b) = gcd (0,d) = b. Thus the algorithm is correct is correct in the basis step.

Assume that the algorithm is correct for all nonnegative integers up to k with k > 1 and .

It is required to prove that the algorithm is also correct for k + 1 with b > k + 1 .

$\mathbf{g}\mathbf{c}\mathbf{d}(k+1,b)=\gcd (bmodk+1,k+1)$

Since (b mod k + 1) < k + 1. (b mod k + 1) < kUsing the inductive hypothesis, it is known that gcd (b mod k + 1, k + 1) is truly the greatest common divisor of b mod k + 1 , and k + 1 .

But then by gcd ( k + 1, b) = gcd (b mod k k + 1, k + 1), the result is also the greatest common divisor of k + 1 and b . Therefore, the algorithm is correct for k + 1.

Hence, by the principle of strong induction, the recursive algorithm is correct.