# 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.
• Note that you're always decreasing the larger of a and b, so you can give a tighter bound than this. Jun 18 '18 at 15:23
Assuming that you start with positive integers, your reasoning is correct. max(a,b) strictly decreases and the loop will terminate before this value reaches zero (since the only way for it to become zero is if a == b). Therefore it can run for at most max(a,b)-1 steps