 Each step begins with two nonnegative remainders "r""k"−1 and "r""k"−2.Since the algorithm ensures that the remainders decrease steadily with every step, "r""k"−1 is less than its predecessor "r""k"−2.The goal of the "k"th step is to find a quotient "q""k" and remainder "r""k" that satisfy the equation

and that have 0 ≤ "r""k" "k"−1.