 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".