In the second step, any natural number "c" that divides both "a" and "b" (in other words, any common divisor of "a" and "b") divides the remainders "r""k". By definition, "a" and "b" can be written as multiples of "c" : "a" = "mc" and "b" = "nc", where "m" and "n" are natural numbers. Therefore, "c" divides the initial remainder "r"0, since "r"0 = "a" − "q"0"b" = "mc" − "q"0"nc" = ("m" − "q"0"n")"c". An analogous argument shows that "c" also divides the subsequent remainders "r"1, "r"2, etc. Therefore, the greatest common divisor "g" must divide "r""N"−1, which implies that "g" ≤ "r""N"−1. Since the first part of the argument showed the reverse ("r""N"−1 ≤ "g"), it follows that "g" = "r""N"−1. Thus, "g" is the greatest common divisor of all the succeeding pairs: