 At every step "k", the Euclidean algorithm computes a quotient "q""k" and remainder "r""k" from two numbers "r""k"−1 and "r""k"−2

where the "r""k" is non-negative and is strictly less than the absolute value of "r""k"−1.The theorem which underlies the definition of the Euclidean division ensures that such a quotient and remainder always exist and are unique.In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, "r""k"−1 is subtracted from "r""k"−2 repeatedly until the remainder "r""k" is smaller than "r""k"−1.