Euclidean division is the decomposition of an integer into an integer multiple of a nonzero integer , together with a remainder:
The integers and are called the quotient and remainder, respectively. For every permitted pair , they exist and are unique. This statement, often called the division algorithm, is a foundational result in arithmetic and number theory. Despite the traditional name, the theorem specifies the result of division rather than a particular procedure for computing it.
Definition and examples
In the equation , is the dividend and is the divisor. The notation denotes the absolute value of the divisor. The restriction on the remainder is essential: without it, many pairs of integers would satisfy the same equation.
For example,
Thus dividing by gives quotient and remainder . Although is also true, it is not a Euclidean division because is not smaller than .
The definition also applies to negative dividends and divisors:
| Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|
In particular,
rather than the expression , whose remainder is negative.
When , the division is exact: divides . When , both quotient and remainder are zero for every nonzero divisor. A zero divisor is excluded; the condition cannot hold when .
Existence and uniqueness
The theorem has two distinct parts: a suitable pair always exists, and no other pair satisfies the same requirements.
Existence
First suppose . Consider the set of all nonnegative integers of the form
This set is nonempty because sufficiently negative values of make nonnegative. By the well-ordering property of the nonnegative integers, it has a least element . Write
for the corresponding integer .
If , then
would be a smaller nonnegative element of the same set, a contradiction. Therefore , as required.
If , apply the positive-divisor case to :
Since , taking gives .
Uniqueness
Suppose two decompositions satisfy the required conditions:
Subtracting gives
The right-hand side has absolute value less than , whereas every nonzero integer multiple of has absolute value at least . Both sides must therefore be zero. Hence and .
This proof explains why both the remainder bound and the exclusion of a zero divisor are necessary.
Relation to ordinary division and rounding
For a positive divisor , the quotient is the floor of the ordinary quotient:
Here the floor of a real number is the greatest integer not exceeding it. For a negative divisor,
where the ceiling is the least integer not smaller than its argument.
Euclidean division differs from division in the rational numbers. Ordinary division retains the entire value ; Euclidean division separates it into an integer quotient and a remainder:
For positive , the term lies between and , with excluded.
Computation
For nonnegative dividends and positive divisors, repeated subtraction provides a simple procedure: repeatedly subtract from until the remaining value is less than . The number of subtractions is the quotient. This procedure is correct but inefficient when the quotient is large.
Long division instead processes the digits of a number in positional notation. At each stage, a partial dividend is divided by the divisor, producing a quotient digit and a smaller remainder. Binary long division uses the same principle with binary digits.
Computer implementations use various algorithms, depending on operand size and hardware. For large integers, efficient division can use approximation and fast multiplication, followed by correction steps that ensure the exact quotient and remainder conditions.
Programming-language conventions
An operation called “integer division,” “remainder,” or “modulo” does not necessarily implement Euclidean division for negative operands.
Three conventions commonly distinguished are:
- Euclidean division: the remainder satisfies .
- Truncating division: the quotient is rounded toward zero; a nonzero remainder has the dividend’s sign.
- Floor division: the quotient is rounded toward negative infinity; a nonzero remainder has the divisor’s sign.
For example, with dividend and divisor , truncating division gives quotient and remainder , whereas Euclidean division gives quotient and remainder . With a positive divisor, floor division agrees with Euclidean division; with a negative divisor, it need not.
These distinctions matter in indexing, cyclic calculations, and implementations of number-theoretic algorithms. Floating-point arithmetic introduces separate rounding considerations and should not be assumed to reproduce exact integer division merely by rounding a floating-point quotient.
Applications in number theory
Modular arithmetic
For a positive integer , Euclidean division assigns every integer a unique remainder among
This provides a standard representative for each equivalence class in modular arithmetic. Two integers have the same remainder precisely when their difference is divisible by :
The representative is an ordinary integer, while the congruence class contains infinitely many integers. Distinguishing these objects clarifies the difference between taking a remainder and working with congruences.
Greatest common divisors
If , then
Indeed, an integer divides both and exactly when it divides both and .
Repeated Euclidean division is therefore the basis of the Euclidean algorithm for finding the greatest common divisor. With positive divisors, successive nonzero remainders strictly decrease, so the process terminates. The last nonzero remainder is the greatest common divisor.
The name connects division with remainder to the arithmetic procedures associated with Euclid and presented in Euclid’s Elements.
Numeral representations
Repeated division by an integer base produces the digits of a nonnegative integer. Each remainder lies between and ; the digits are obtained from least significant to most significant. Repeated division by , for example, yields decimal digits.
Polynomial division and algebraic generalization
A parallel theorem holds for polynomials over a field. Given polynomials and nonzero , there are unique polynomials and such that
where either or
Polynomial degree replaces the size bound on an integer remainder. The coefficient field permits division by the leading coefficient of , allowing successive cancellation of leading terms.
The field assumption matters. Division by an arbitrary polynomial need not be possible with integer coefficients. For example, dividing by would require the quotient to leave a remainder of degree less than one. Division by a monic polynomial, however, works over any commutative coefficient ring with identity.
In abstract algebra, a Euclidean domain is an integral domain equipped with a size function on its nonzero elements that permits division with a remainder of smaller size, or remainder zero. The integers and polynomial rings over fields are standard examples. In general Euclidean domains, the size condition need not make quotient and remainder unique; that uniqueness is an additional feature of the familiar integer and polynomial versions.