 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".To demonstrate that "r""N"−1 divides both "a" and "b" (the first step), "r""N"−1 divides its predecessor "r""N"−2

since the final remainder "r""N" is zero.