stylistic:tone, information:filtering
Euclidean division

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

where the r is non-negative and is strictly less than the absolute value of r. 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 is subtracted from r repeatedly until the remainder r is smaller than r. After that r and r are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply