The validity of the Euclidean algorithm can be proven by a two-step argument. In the first step, the final nonzero remainder "r""N"−1 is shown to divide both "a" and "b". Since it is a common divisor, it must be less than or equal to the greatest common divisor "g". In the second step, it is shown that any common divisor of "a" and "b", including "g", must divide "r""N"−1; therefore, "g" must be less than or equal to "r""N"−1. These two conclusions are inconsistent unless "r""N"−1 = "g".