A hundred eggs are packed into cartons of twelve. Eight cartons fill up and four eggs are left over, which is the statement
$$100 = 12 \cdot 8 + 4.$$
But can it always be done, for negative numbers too, and is there only ever one right answer?
The division algorithm says yes to both. For any integer $a$ and any positive integer $b$, there is exactly one way to write $a = bq + r$ with a remainder $r$ satisfying $0 \le r < b$. The name is traditional and slightly misleading: the result is a theorem, not a procedure, although its proof suggests a procedure and the next article turns it into one.
The statement looks too familiar to need proof, and that is the reason to prove it carefully. It is the first place where the course takes a fact from school arithmetic and asks what it rests on. The answer is a single property of the nonnegative integers, the well-ordering principle, which also underlies proof by induction. Nearly everything in this unit follows from the division algorithm:
- greatest common divisors and the Euclidean algorithm;
- the unique factorization of integers into primes;
- the arithmetic of remainders that becomes the ring $\mathbb{Z}_n$.
The same statement for polynomials drives the second half of the ring theory in the course, and later articles cite this one rather than repeat it.
First we state the well-ordering principle. Then we prove that a remainder exists and that it is unique. Next we read the theorem as a picture and a formula, and see why programming languages disagree about negative numbers. Finally we sort the integers by remainder and use the sorting on last digits. The small examples let us list every candidate remainder; the unit's running pair, 1729 and 1001, appears in the checks.
This is the first article of Arithmetic in the Integers, the first unit of the course notes for MTH 532, Abstract Algebra. In the course text it is §1.1 (Hungerford, 2014, Theorem 1.1).
The well-ordering principle
Throughout, $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ is the set of integers with its usual addition, multiplication and order. The proofs in this unit use the ordinary rules of arithmetic and inequalities freely, together with one further property of the integers.
Well-ordering principle. Every nonempty set of nonnegative integers has a least element.
The principle is taken as an axiom about the integers, alongside the rules of arithmetic. It is equivalent to the principle of mathematical induction: either one can be proved from the other (Judson, 2026, §2.1). So a reader who prefers induction as the starting point loses nothing.
The hypothesis "nonnegative" matters. The set of negative integers is nonempty and has no least element, since below any negative integer $m$ lies $m - 1$. The integers themselves are not well ordered, and neither are the rationals, even the positive ones. The set $\{x \in \mathbb{Q} : x > 3\}$ has no least element: for any rational $x > 3$, the average $(x + 3)/2$ is again rational, again greater than 3, and smaller than $x$. Well-ordering is a property of the integers that the rationals and reals lack, and it is the property that makes remainders exist.
Statement of the theorem
Theorem (division algorithm). Let $a$ and $b$ be integers with $b > 0$. There exist unique integers $q$ and $r$ such that
$$a = bq + r \quad \text{and} \quad 0 \le r < b.$$
The integer $q$ is the quotient and $r$ the remainder when $a$ is divided by $b$. The number $a$ is the dividend and $b$ the divisor.
The theorem makes two claims. Existence says that a suitable pair $q, r$ can be found. Uniqueness says that only one pair works, which is what entitles us to speak of the quotient and the remainder. Both claims depend on the condition $0 \le r < b$. Without it, the equation $a = bq + r$ alone says almost nothing, since any $q$ can be chosen and $r$ defined as $a - bq$. For $a = 100$ and $b = 12$:
| $q$ | $r = 100 - 12q$ | $0 \le r < 12$? |
|---|---|---|
| 6 | 28 | no |
| 7 | 16 | no |
| 8 | 4 | yes |
| 9 | $-8$ | no |
| 10 | $-20$ | no |
Raising $q$ by one lowers $r$ by $b$. So the possible values of $r$ step through the integers in strides of 12, and exactly one of them lands in the window from 0 to 11. The two proofs that follow make this picture rigorous, one claim at a time.
Proof of existence
The idea is to take the smallest candidate $a - bk$ that is not negative, which well-ordering provides; if it were $b$ or more, subtracting $b$ once more would give a smaller one.
Proof. Let
$$S = \{\, a - bk : k \in \mathbb{Z} \text{ and } a - bk \ge 0 \,\},$$
the set of nonnegative values that $a - bk$ takes as $k$ ranges over the integers.
$S$ is not empty. Take $k = -\lvert a \rvert$. Then $a - bk = a + b\lvert a \rvert$. Since $b \ge 1$, we have $b \lvert a \rvert \ge \lvert a \rvert$, so $a + b \lvert a \rvert \ge a + \lvert a \rvert \ge 0$. Hence this value belongs to $S$.
$S$ has a least element. $S$ is a nonempty set of nonnegative integers, so by the well-ordering principle it has a least element. Call it $r$, and let $q$ be an integer for which $r = a - bq$. Then $a = bq + r$ and $r \ge 0$.
The least element is less than $b$. Suppose instead that $r \ge b$. Then
$$a - b(q + 1) = (a - bq) - b = r - b \ge 0,$$
so $r - b$ is also an element of $S$, with $k = q + 1$. But $r - b < r$ because $b > 0$, which contradicts the choice of $r$ as the least element of $S$. Therefore $r < b$, and the pair $q, r$ satisfies $a = bq + r$ and $0 \le r < b$. $\blacksquare$
For $a = 100$ and $b = 12$, the set $S$ is $\{4, 16, 28, 40, \ldots\}$, and its least element 4 comes from $k = 8$. For $a = -100$ the candidates are $-100 - 12k$, which are nonnegative only for $k \le -9$. Then $S = \{8, 20, 32, \ldots\}$, its least element 8 comes from $k = -9$, and
$$-100 = 12 \cdot (-9) + 8.$$
The remainder of a negative number is still nonnegative, so the quotient is $-9$, one less than the $-8$ that a calculator's $-100/12 = -8.33\ldots$ might suggest.
Check your understanding. Dividing 1729 by 1001 leaves quotient 1 and remainder 728. Without dividing again, what are the quotient and remainder of $-1729$? A calculator shows $-1729/1001 = -1.727\ldots$; is the quotient $-1$?
It is not. Negating $1729 = 1001 \cdot 1 + 728$ gives $-1729 = 1001 \cdot (-1) - 728$, and $-728$ is not an allowed remainder. Borrowing one more 1001 fixes that: $-1729 = 1001 \cdot (-2) + (1001 - 728) = 1001 \cdot (-2) + 273$. In general, if $a$ leaves a nonzero remainder $r$, then $-a$ leaves $b - r$, as 100 and $-100$ leave 4 and 8 on division by 12.
Proof of uniqueness
Could a different choice of $k$ also land in the window? The idea is that two remainders in a window of width $b$ differ by less than $b$, yet their difference is a multiple of $b$, and the only such multiple is 0.
Proof. Suppose that two pairs both work:
$$a = bq + r, \quad 0 \le r < b \qquad \text{and} \qquad a = bq' + r', \quad 0 \le r' < b.$$
Subtracting the two expressions for $a$ gives $0 = b(q - q') + (r - r')$, that is,
$$b(q - q') = r' - r.$$
Both remainders lie in the interval from $0$ to $b - 1$, so their difference satisfies $-b < r' - r < b$. Hence $-b < b(q - q') < b$, and dividing by the positive number $b$ gives $-1 < q - q' < 1$. The only integer strictly between $-1$ and $1$ is $0$, so $q = q'$. Then $r' - r = b \cdot 0 = 0$, so $r = r'$. $\blacksquare$
In the table for 100 and 12, the candidates are spaced 12 apart, so at most one fits. The two halves of the proof use different facts. Existence needs well-ordering, and uniqueness needs only the length of the window $0 \le r < b$. So any window of $b$ consecutive integers would give existence and uniqueness equally well. The window $-b/2 < r \le b/2$, for instance, gives the remainder of smallest absolute value. The convention $0 \le r < b$ is the standard one, and it is the one used throughout these notes.
Check your understanding. In the window $-b/2 < r \le b/2$, what is the remainder of 100 divided by 12? Of 1729 divided by 1001?
For 100 it is still 4, which already lies between $-6$ and $6$. For 1729 it changes: 728 is more than half of 1001, so the quotient goes up by one and $1729 = 1001 \cdot 2 + (-273)$. The window decides which remainder we get, but each window gives exactly one.
A picture and a formula
The multiples of $b$ divide the number line into consecutive intervals $[bq, bq + b)$ of length $b$, and every integer falls in exactly one of them. The division algorithm names that interval: $bq$ is the largest multiple of $b$ that does not exceed $a$, and $r$ is the distance from $bq$ up to $a$.
The picture gives a formula. Dividing $a = bq + r$ by $b$ gives
$$\frac{a}{b} = q + \frac{r}{b}, \qquad 0 \le \frac{r}{b} < 1.$$
So $q$ is the greatest integer not exceeding $a/b$, written $\lfloor a/b \rfloor$ (the floor of $a/b$), and $r = a - b\lfloor a/b \rfloor$. For $a = 23$ and $b = 7$, $a/b = 3.29\ldots$, so $q = 3$ and $r = 23 - 21 = 2$. For $a = -23$, $a/b = -3.29\ldots$, whose floor is $-4$, so $q = -4$ and $r = -23 + 28 = 5$. The script for this article checks that the floor formula agrees with the theorem for every $a$ with $\lvert a \rvert \le 300$ and every $b$ from 1 to 39.
The formula is a convenient way to compute $q$, but it is not a proof that $q$ exists. The existence of the floor of a rational number is itself a consequence of well-ordering.
Negative numbers in programming languages
The floor formula raises a practical question: do computers use it? Programming languages provide integer division and remainder operators, and they do not all agree with the theorem.
- The C standard specifies that integer division discards the fractional part of the exact quotient. The standard's footnote calls this "truncation toward zero", and it requires
(a/b)*b + a%bto equala(ISO/IEC 9899:2011, §6.5.5). - Python's
//applies the floor to the exact quotient, and its%returns a result "with the same sign as its second operand" (Python Language Reference, §6.7).
Both satisfy $a = bq + r$. They differ in which $q$ they choose, and therefore in the sign of $r$.
| $a$ | $b$ | Python a // b, a % b |
C a / b, a % b |
Theorem, $0 \le r < \lvert b \rvert$ |
|---|---|---|---|---|
| 23 | 7 | 3, 2 | 3, 2 | 3, 2 |
| $-23$ | 7 | $-4$, 5 | $-3$, $-2$ | $-4$, 5 |
| 23 | $-7$ | $-4$, $-5$ | $-3$, 2 | $-3$, 2 |
| $-23$ | $-7$ | 3, $-2$ | 3, $-2$ | 4, 5 |
For a positive divisor, Python agrees with the theorem, and C does not when the dividend is negative. A program that computes a day of the week as n % 7 in C can produce negative "days" for negative n. On the running example, Python's -1729 % 1001 is 273, as in the check above, while C gives $-728$.
The last column extends the theorem to negative divisors: for any nonzero $b$ there are unique $q$ and $r$ with $a = bq + r$ and $0 \le r < \lvert b \rvert$, by the theorem applied to $\lvert b \rvert$. Neither language implements that convention for negative divisors. In these notes divisors are positive unless stated otherwise.
Remainders sort the integers
What happens when we fix the divisor and divide every integer by it? Fix a positive integer $n$. By the division algorithm, every integer $a$ has exactly one remainder on division by $n$, one of $0, 1, \ldots, n - 1$. So every integer has exactly one of the forms
$$nk, \quad nk + 1, \quad nk + 2, \quad \ldots, \quad nk + (n - 1)$$
for some integer $k$. The integers fall into $n$ disjoint classes according to remainder. For $n = 5$:
| Remainder | Integers from $-10$ to $14$ with that remainder |
|---|---|
| 0 | $-10, -5, 0, 5, 10$ |
| 1 | $-9, -4, 1, 6, 11$ |
| 2 | $-8, -3, 2, 7, 12$ |
| 3 | $-7, -2, 3, 8, 13$ |
| 4 | $-6, -1, 4, 9, 14$ |
Within each row, neighbors differ by 5. That is no accident, and it is the content of the next result. This sorting of the integers is the seed of congruence modulo $n$. There each row becomes a single object, a congruence class, and the classes are added and multiplied as elements of the ring $\mathbb{Z}_5$.
Same remainder, difference a multiple
Proposition. Fix a positive integer $n$. Two integers have equal remainders on division by $n$ exactly when their difference is a multiple of $n$.
The idea is that subtracting two divisions with the same remainder cancels the remainders. Conversely, adding a multiple of $n$ only shifts the quotient, and uniqueness says the remainder is unchanged.
Proof. Call the two integers $a$ and $c$. Suppose first that $a$ and $c$ leave the same remainder $r$. By the division algorithm, $a = nq_1 + r$ and $c = nq_2 + r$ for some integers $q_1$ and $q_2$. Subtracting, $a - c = n(q_1 - q_2)$, and $q_1 - q_2$ is an integer.
Conversely, suppose $a - c = nk$ for an integer $k$. Divide $c$ by $n$: $c = nq + r$ with $0 \le r < n$. Then
$$a = c + nk = n(q + k) + r, \qquad 0 \le r < n.$$
This expresses $a$ in exactly the form the division algorithm describes, with quotient $q + k$ and remainder $r$. By the uniqueness half of the theorem, it is the division of $a$ by $n$. So the remainder of $a$ is $r$, the same as the remainder of $c$. $\blacksquare$
For example, $38 = 12 \cdot 3 + 2$ and $-22 = 12 \cdot (-2) + 2$ both leave remainder 2 on division by 12, and their difference is $60 = 12 \cdot 5$. The second half of the proof is where uniqueness earns its keep. Finding some expression $a = n(q + k) + r$ with $0 \le r < n$ settles what the remainder of $a$ is.
Check your understanding. The difference $1729 - 1001 = 728$ factors as $2^3 \cdot 7 \cdot 13$. Without dividing, do 1729 and 1001 leave the same remainder on division by 13, by 8, or by 12?
By 13 and by 8 they do, because 728 is a multiple of each (the remainders are 0 and 1). By 12 they do not, because 728 is not a multiple of 12: 1729 leaves 1 and 1001 leaves 5.
The proposition says that adding a multiple of $n$ never changes the remainder. Two consequences are used constantly.
Remainders of sums and products. If $a$ leaves remainder $r$ and $c$ leaves remainder $s$ on division by $n$, then $a + c$ leaves the same remainder as $r + s$, and $ac$ leaves the same remainder as $rs$. The idea: $a$ differs from $r$, and $c$ from $s$, by multiples of $n$, and multiplying out keeps every extra term a multiple of $n$. For products, write $a = nq_1 + r$ and $c = nq_2 + s$. Then
$$ac = n^2 q_1 q_2 + n q_1 s + n q_2 r + rs = n(nq_1q_2 + q_1 s + q_2 r) + rs,$$
so $ac - rs$ is a multiple of $n$, and the proposition applies. The argument for sums is the same with one line of algebra. To find a remainder of a large expression, it is enough to work with the small remainders.
Application: last digits
For a nonnegative integer, the last decimal digit is the remainder on division by 10. Which digits can end a perfect square?
Write any integer $m$ as $m = 10q + r$ with $0 \le r \le 9$. By the product rule just shown, $m^2$ leaves the same remainder on division by 10 as $r^2$. So the last digit of $m^2$ is the last digit of $r^2$, and there are only ten cases to check:
| $r$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| last digit of $r^2$ | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 |
So a perfect square ends in 0, 1, 4, 5, 6 or 9, and never in 2, 3, 7 or 8. Without any arithmetic beyond reading the last digit, 123457 is not a perfect square. (The case analysis covers negative $m$ as well, since $m^2 = (-m)^2$.)
This is the method of proof by cases on the remainder. The division algorithm splits the integers into finitely many classes, and a question about all integers reduces to one check per class.
Check your understanding. The number 1729 ends in 9, an allowed last digit, so is it a perfect square?
It is not, since $41^2 = 1681$ and $42^2 = 1764$. The last-digit test can rule a number out, but passing it proves nothing: every square passes, and so do many numbers that are not squares.
Powers repeat in the same way. The last digits of $7, 7^2, 7^3, 7^4$ are $7, 9, 3, 1$. Since $7^4 = 2401$, the difference $7^{k+4} - 7^k = 7^k(7^4 - 1) = 7^k \cdot 2400$ is a multiple of 10 for every $k \ge 1$. By the proposition, $7^{k+4}$ and $7^k$ have the same last digit, so the pattern $7, 9, 3, 1$ repeats with period 4.
To find the last digit of $7^{2026}$, divide the exponent by the period: $2026 = 4 \cdot 506 + 2$. So $7^{2026}$ ends in the same digit as $7^2 = 49$, namely 9. The script for this article confirms this from the full 1,713-digit integer. This is the first appearance of a recurring idea: an exponent matters only through its remainder on division by the period. That principle is behind Fermat's little theorem and the RSA cryptosystem.
Why "algorithm"
Where is the procedure the name promises? The existence proof hides one: subtract $b$ from $a$ repeatedly (or add it, if $a$ is negative) until the result lands in the window $0 \le r < b$, and count the steps to get $q$.
That procedure is correct but slow, because it takes $\lvert q \rvert$ steps or more. Dividing $1{,}000{,}003$ by 7 this way takes 142,857 subtractions, which leave remainder 4. School long division finds the same answer by working one decimal digit of the quotient at a time. So its work grows with the number of digits of $a$ rather than with its size. Computers do the same in base 2. Either way, the theorem guarantees that the procedure has a single correct answer to find.
Where it leads
The division algorithm is used throughout the course:
- The Euclidean algorithm for greatest common divisors is the division algorithm applied repeatedly. Its correctness rests on the fact that the common divisors of $a$ and $b$ are the common divisors of $b$ and $r$ (Divisibility and the Euclidean Algorithm).
- Unique factorization into primes rests on the greatest common divisor, and so on the division algorithm (Primes and the Fundamental Theorem of Arithmetic).
- The classes of integers with a common remainder become the elements of $\mathbb{Z}_n$ (Congruence Modulo n, The Integers Modulo n).
- For polynomials with coefficients in a field, the same theorem holds with degree in place of size (Polynomial Division over a Field). Rings with a division algorithm of this kind are called Euclidean domains. In them every ideal is generated by a single element, the property that principal ideal domains are named for.
What we have learned
Division with remainder always has exactly one answer once the remainder must lie in $0 \le r < b$. Existence came from well-ordering, uniqueness from the width of the window. Uniqueness also shows that two integers share a remainder exactly when their difference is a multiple of the divisor. That turns questions about all integers, such as which digits can end a square, into a finite check.
The first division in the running example is $1729 = 1001 \cdot 1 + 728$. What if we keep going, dividing 1001 by 728 and so on? That repeated division finds the greatest common divisor of 1729 and 1001, the subject of Divisibility and the Euclidean Algorithm.
References
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §1.1. Brooks/Cole, Cengage Learning. The course text; the division algorithm is its Theorem 1.1. record · 44 pages
- ISO/IEC 9899:2011. Information technology: Programming languages: C, §6.5.5 (multiplicative operators). Cited from the final committee draft, WG14 N1570 (April 2011). record · 2 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §2.1 (mathematical induction and the principle of well-ordering) and §2.2 (the division algorithm). Free online at judsonbooks.org. record · 44 pages
- Python Software Foundation. The Python Language Reference, §6.7, Binary arithmetic operations. docs.python.org/3/reference/expressions.html. record