 Since the remainders decrease with every step but can never be negative, a remainder "r""N" must eventually equal zero, at which point the algorithm stops.The final nonzero remainder "r""N"−1 is the greatest common divisor of "a" and "b".The number "N" cannot be infinite because there are only a finite number of nonnegative integers between the initial remainder "r"0 and zero.