Section 2.3 More on Proof of Correctness
135
Then
gcd(i k+1 , j k+1 ) = gcd( j k , r k )
= gcd(i k , j k )
by (5)
= gcd(a, b)
by the inductive hypothesis
Q is therefore a loop invariant. At loop termination, gcd(i, j) = gcd(a, b) and j = 0,
so gcd(i, 0) = gcd(a, b). But gcd(i, 0) is i, so i = gcd(a, b). Therefore function
GCD is correct.