134
Proofs, Induction, and Number Theory
while j ≠ 0 do
compute i = q j + r, 0 ≤ r < j
i = j
j = r
end while
// i now has the value gcd(a, b)
return i;
end function GCD
We intend to prove the correctness of this function, but we will need one additional fact first, namely,
(4 integers a, b, q, r)3(a = qb + r) S (gcd(a, b) = gcd(b, r))4
(5)
To prove (5), assume that a = qb + r and suppose that c divides both a and b so
that a = q 1 c and b = q 2 c. Then
r = a − qb = q 1 c − qq 2 c = c (q 1 − qq 2 )
so that c divides r as well. Therefore anything that divides a and b also divides b
and r. Now suppose d divides both b and r so that b = q 3 d and r = q 4 d. Then
a = qb + r = qq 3 d + q 4 d = d(qq 3 + q 4 )
so that d divides a as well. Therefore anything that divides b and r also divides a
and b. Because (a, b) and (b, r) have identical divisors, they must have the same
greatest common divisor.
eXAMPLe 28
Prove the correctness of the Euclidean algorithm.
Using function GCD, we will prove the loop invariant Q: gcd(i, j) = gcd(a, b)
and evaluate Q when the loop terminates. We use induction to prove Q(n):
gcd(i n , j n ) = gcd(a, b) for all n ≥ 0. Q(0) is the statement
gcd(i 0 , j 0 ) = gcd(a, b)
which is true because when we first get to the loop statement, i and j have the values a and b, respectively.
Assume Q(k): gcd(i k , j k ) = gcd(a, b)
Show Q(k + 1): gcd(i k+1 , j k+1 ) = gcd(a, b)
By the assignment statements within the loop body, we know that
i k+1 = j k
j k+1 = r k