Euclidean division
Given two integers a and b with b ≠ 0, there exist unique integers q and r, called respectively the quotient and the remainder, such that $$ a = b \cdot q + r $$
This statement formalizes a familiar idea: when one integer is divided by another, the result can always be expressed as a whole-number part and a leftover.
The remainder is constrained by the inequality
$$ 0 \le r < |b| $$
If the remainder is zero, the division is exact, and a is said to be divisible by b.
A concrete example
Let us look at a simple numerical case with a = 3 and b = 8.
The integer 3 does not divide 8 evenly.
As a result, dividing 8 by 3 produces a nonzero remainder, namely r = 2.
$$ b = a \cdot q + r \\ 8 = 3 \cdot q + r \\ 8 = 3 \cdot 2 + 2 $$
In this case, the quotient is q = 2 and the remainder is r = 2.
As required by the definition, the remainder is a nonnegative integer strictly smaller than |8|.
Proof and explanation
Existence proof
To justify the definition rigorously, consider the set of all integers of the form a - nb that are nonnegative, where n ranges over all integers.
$$ S = \{ a - nb \:\: | \:\: n \in Z , \, a - nb \ge 0 \} $$
This set is guaranteed to be nonempty. For example, if n = a, then
$$ a - nb = a - ab = a(1 - b) $$
and if n = -a, then
$$ a - nb = a - (-a)b = a(1 + b) $$
Since b is nonzero, at least one of these expressions is nonnegative, ensuring that S contains at least one element.
Example. Take a = 3 and b = 5. We check explicitly that the set S = { a - nb ≥ 0 } is not empty. $$ S = \{ a - nb \} = \{ 3 - n \cdot 5 \ge 0 \} $$ For n = a = 3 we obtain $$ 3 - n \cdot 5 = 3 - 3 \cdot 5 = -12 $$ whereas for n = -a = -3 we obtain $$ 3 - n \cdot 5 = 3 - (-3) \cdot 5 = 18 \ge 0 $$ Choosing n = -a satisfies the defining condition, so the set S is indeed nonempty.
Because S is a nonempty subset of the nonnegative integers, it has a smallest element. Denote this minimum by r, and let q be the corresponding integer such that
$$ r = a - qb $$
This value r will turn out to be the remainder of the division.
We now show that r must satisfy the upper bound r < |b|.
Assume, for the sake of contradiction, that
$$ r \ge |b| $$
Then the difference
$$ r - |b| \ge 0 $$
is also nonnegative. Let us denote this new quantity by r'.
$$ r' = r - |b| \ge 0 $$
Substituting r = a - qb into this expression gives
$$ r' = (a - qb) - |b| $$
After a simple algebraic rearrangement, this can be written as
$$ r' = a - \left( q + \frac{|b|}{b} \right) b $$
Define q' = q + |b|/b. Then
$$ r' = a - q'b \ge 0 $$
which shows that r' also belongs to the set S.
$$ r' \in S $$
However, r' is strictly smaller than r.
$$ r' = r - |b| \Rightarrow r' < r $$
This contradicts the fact that r was chosen as the minimum element of S. Therefore, the assumption is false, and the remainder must satisfy r < |b|.
Uniqueness proof
Finally, we show that the quotient and the remainder are uniquely determined.
Suppose that there exist two pairs (q, r) and (q', r') such that
$$ a = bq + r , \quad 0 \le r < |b| $$
$$ a = bq' + r' , \quad 0 \le r' < |b| $$
Both r and r' are nonnegative integers strictly smaller than |b|.
$$ 0 \le r, r' < |b| $$
Assume without loss of generality that r' ≥ r. Then
$$ 0 \le r' - r \le r' < |b| $$
On the other hand, subtracting the two expressions for a gives
$$ r' - r = a - bq' - (a - bq) = b(q - q') $$
Combining these relations yields
$$ 0 \le b(q - q') \le r' < |b| $$
Taking absolute values, we obtain
$$ 0 \le |b| \cdot |q - q'| \le r' < |b| $$
The only way this inequality can hold is if |q - q'| = 0.
Thus
$$ q = q' $$
Substituting this back into either expression for a immediately gives
$$ r = r' $$
Note. If q = q', then $$ a = bq + r $$ $$ a = bq + r' $$ Solving for the remainders yields $$ r = a - bq $$ $$ r' = a - bq $$ hence $$ r = r' $$
This completes the proof that, in Euclidean division, both the quotient and the remainder are uniquely determined.
And so on.
