Proving GCD algorithm terminates

I'm looking at program 1. In particular I'm trying to understand the proof that the loop terminates. Here is program 1 (my notation is slightly different than the one in the article):

function GCD(a,b)

while a != b
if a > b
a = a - b
else
b = b - a

return a

I get that max(a,b) at loop n is strictly greater than max(a,b) at loop n+1. Since a and b are integers greater than 0 it follows that max(a,b) is always greater than 0. This implies a lower bound. Therefore the while loop must terminate.

Is my understanding correct?

• if a=1 and b=-1 the algorithm wil not terminate. If a,b are positive integers then the max(a,b) will strictly decrease. May 19 '18 at 10:02
• The algorithm doesn't terminate if a ≤ 0 or b ≤ 0 unless initially a = b. May 19 '18 at 10:39

If you just care about termination of the algorithm not the tight analysis then you can say that it will terminates within $a+b$ steps as inside the while loop you are decreasing either $a$ or $b$ depending on some condition, so your while loop have to terminate within $a+b$ iterations.