 Then "a" is the next remainder "r""k".Then "b" is reduced by multiples of "a" until it is again smaller than "a", giving the next remainder "r""k"+1, and so on.The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd("r""N"−1, 0) = "r""N"−1.