Prove correctness of the while loop of Algorithm 4.8.3 (in

Chapter 5, Problem 10E

(choose chapter or problem)

Problem 10E

Prove correctness of the while loop of Algorithm 4.8.3 (in exercise 24 of Exercise Set 4.8) with respect to the following pre- and post-conditions:

Pre-condition: A and B are positive integers,

a = A, and b = B.

Post-condition: One of a or b is zero and the other is nonzero. Whichever is nonzero equals gcd(A, B).

Use the loop invariant

I ( n ) “(1) a and b are nonnegative integers with

gcd(a, b) = gcd(A, B).

(2) at most one of a and b equals 0,

(3) 0 ≤ a + b ≤ A + B − n.”