Euclidean division

In arithmetic, Euclidean division is the process of division of two integers, which produces a quotient and a remainder. This is a theorem that states that the quotient and remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder. The methods of computation are called integer division algorithms, the most well-known being long division.

Euclidean division, and algorithms to compute it, are fundamental for many questions concerning integers, such as the Euclidean algorithm for finding the greatest common divisor of two integers, and modular arithmetic, for which only remainders are considered. The operation consisting in computing only the remainder is called the modulo operation.

Given two integers $a$ and $b$ , with $b \neq 0$ , there exist unique integers $q$ and $r$ such that

and

where $| b |$ denotes the absolute value of $b$ .

The four integers that appear in this theorem have been given names: $a$ is called the dividend, $b$ is called the divisor, $q$ is called the quotient and $r$ is called the remainder.

The computation of the quotient and the remainder from the dividend and the divisor is called division or, in case of ambiguity, Euclidean division. The theorem is frequently referred to as the division algorithm, although it is a theorem and not an algorithm, because its proof as given below also provides a simple division algorithm for computing $q$ and $r$ .

...
Wikipedia