The division algorithm

Theorem

The division algorithm

T-136Home MU-101Threads logic · structure

Statement

Let \( a \in \mathbb{Z} \) and let \( b \in \mathbb{Z} \) with \( b \neq 0 \). Then there exist integers \( q \) and \( r \), and only one such pair, satisfying \[ a = bq + r \qquad\text{and}\qquad 0 \le r \lt |b| . \] The integer \( q \) is called the quotient and \( r \) the remainder of \( a \) on division by \( b \). Explicitly \( q = \lfloor a/b \rfloor \) when \( b \gt 0 \) and \( q = \lceil a/b \rceil \) when \( b \lt 0 \), and in both cases \( r = a - bq \). The name is traditional but misleading: the assertion is a theorem of existence and uniqueness about \( \mathbb{Z} \), not an algorithm, and its proof rests only on the well-ordering of \( \mathbb{Z}_{\ge 0} \).

Why it matters

Almost every construction in elementary number theory is this theorem applied repeatedly. The Euclidean algorithm is nothing but the division algorithm iterated on \( (b, r) \) until the remainder vanishes, and its termination is exactly the strict decrease \( |b| \gt r \ge 0 \) guaranteed here; from that follow Bézout's identity, Euclid's lemma, the Fundamental Theorem of Arithmetic, and the computability of modular inverses. Modular arithmetic itself is a corollary: the theorem is precisely the assertion that the \( n \) residue classes \( \overline{0}, \overline{1}, \ldots, \overline{n-1} \) exhaust \( \mathbb{Z}/n\mathbb{Z} \) without repetition, so that \( |\mathbb{Z}/n\mathbb{Z}| = n \). Positional notation — base \( 10 \), base \( 2 \), base \( 16 \) — is the same theorem applied recursively to successive quotients, which is why every computer's integer arithmetic is built on it.

Structurally, the theorem is the definition of \( \mathbb{Z} \) as a Euclidean domain: an integral domain carrying a size function (here \( n \mapsto |n| \)) with respect to which remainders can always be made strictly smaller than the divisor. Every consequence of that property — that \( \mathbb{Z} \) is a principal ideal domain, hence a unique factorisation domain — is downstream of this one paragraph. The identical statement with \( |n| \) replaced by \( \deg \) holds in \( F[t] \) for a field \( F \), and that single substitution transports the whole of elementary number theory into polynomial algebra: gcds of polynomials, partial fractions, the structure of \( F[t]/(f) \), and the classification of finite fields.

Hypotheses

\( b \neq 0 \). For \( b = 0 \) the condition \( 0 \le r \lt |b| = 0 \) describes an empty set of integers, so no admissible remainder exists and the existence claim fails outright — for every \( q \) the equation \( a = 0\cdot q + r \) forces \( r = a \), which is never in the empty range. Note that \( b \) may be negative; only \( 0 \) is excluded.

The remainder is confined to \( 0 \le r \lt |b| \). This constraint is the entire content of the uniqueness half, not decoration. Drop it and every \( q \in \mathbb{Z} \) works: \( 17 = 5\cdot 3 + 2 = 5\cdot 2 + 7 = 5\cdot(-1) + 22 \) are all valid representations of the form \( a = bq+r \). Any interval of exactly \( |b| \) consecutive integers would serve equally well (see the balanced variant in Problem 5); the choice \( [0, |b|) \) is a convention, and it is the convention that makes \( r \) the canonical representative of \( a \) modulo \( b \).

\( a \) and \( b \) are integers, not elements of a field. In \( \mathbb{Q} \) or \( \mathbb{R} \) every non-zero \( b \) is invertible, so \( a = b(a/b) + 0 \) always holds with \( r = 0 \); but \( a = b\cdot 0 + a \) with \( 0 \le a \lt |b| \) is also admissible whenever \( 0 \le a \lt |b| \), and for \( a=1, b=2 \) both \( (q,r) = (1/2, 0) \) and \( (q,r) = (0,1) \) satisfy the displayed conditions. Uniqueness dies immediately: the discreteness of \( \mathbb{Z} \) is doing real work.

\( \mathbb{Z}_{\ge 0} \) is well-ordered. Existence is proved by taking the least element of a set of candidate remainders. Without well-ordering — equivalently, without induction over the base theory — that set need not attain its lower bound, and no remainder is produced. \( \mathbb{Q}_{\ge 0} \) shows how ordinary the failure is: \( \{\, q \in \mathbb{Q} : q \gt 0 \,\} \) is bounded below yet has no minimum. The explicit division-algorithm counterexample is in Fails without.

Proof

We prove existence first for \( b \gt 0 \), then uniqueness in the same range, then reduce the case \( b \lt 0 \) to it by a sign change. Throughout, \( q \) and \( r \) denote integers and every inequality is an inequality of integers, so that “strictly smaller non-negative integer” carries its full force.

Assume \( b \gt 0 \) and set \[ S \;=\; \{\, a - bk \;:\; k \in \mathbb{Z} \,\} \cap \mathbb{Z}_{\ge 0} \;=\; \{\, s \in \mathbb{Z}_{\ge 0} : s = a - bk \text{ for some } k \in \mathbb{Z} \,\} . \]

\( S \) collects exactly the non-negative values that survive after subtracting some integer multiple of \( b \) from \( a \). A remainder, if one exists, must lie in \( S \) by definition; the strategy is to show the smallest member of \( S \) is one. A

\( S \neq \emptyset \). Take \( k = -|a| \); then \[ a - bk \;=\; a + b|a| \;\ge\; a + |a| \;\ge\; 0 , \] since \( b \ge 1 \) and \( |a| \ge 0 \) give \( b|a| \ge |a| \), while \( a + |a| \) is \( 2a \ge 0 \) if \( a \ge 0 \) and \( 0 \) if \( a \lt 0 \).

Non-emptiness must be established before well-ordering can be invoked — this is the step everyone skips. The witness is explicit, so no appeal to any existence principle is smuggled in here. Note where the hypothesis \( b \gt 0 \) is consumed: it is what turns \( b|a| \) into something at least \( |a| \). B

By the well-ordering principle \( S \) has a least element. Call it \( r \), and let \( q \in \mathbb{Z} \) be a witness to its membership, so that \[ r = a - bq \ge 0, \qquad\text{i.e.}\qquad a = bq + r . \]

\( S \) is a non-empty subset of \( \mathbb{Z}_{\ge 0} \), so well-ordering applies verbatim. The existence half of the theorem is now reduced to a single inequality, \( r \lt b \). A

Claim \( r \lt b \). Suppose instead \( r \ge b \). Then \( r - b \ge 0 \) and \[ r - b \;=\; (a - bq) - b \;=\; a - b(q+1) , \] so \( r - b \in S \); but \( b \gt 0 \) gives \( r - b \lt r \), contradicting the minimality of \( r \). Hence \( 0 \le r \lt b \) and existence is proved.

The descent step, and the whole idea of the proof: an over-large remainder can always be reduced by subtracting one more copy of \( b \), so the least element cannot be over-large. This is where \( b \gt 0 \) does its work — it is what makes \( r - b \) strictly smaller than \( r \), so that the contradiction with minimality is genuine rather than vacuous. B

Uniqueness, still for \( b \gt 0 \). Suppose \( (q,r) \) and \( (q', r') \) both satisfy the conclusion. Subtracting the two equations, \[ b(q - q') = r' - r . \]

Symbols are rearranged before any numbers are considered: the difference of two representations isolates a multiple of \( b \) on the left and a difference of two admissible remainders on the right. Everything now follows from bounding the right-hand side. A

From \( 0 \le r \lt b \) and \( 0 \le r' \lt b \) we get \( -b \lt r' - r \lt b \), i.e. \( |r' - r| \lt b \). Combining with Step 5, \[ |b|\,|q - q'| \;=\; |r' - r| \;\lt\; b \;=\; |b| \quad\Longrightarrow\quad |q - q'| \lt 1 .\]

Inequalities may not be subtracted termwise; the legal move is to negate one and add. From \( 0 \le r \lt b \) we get \( -b \lt -r \le 0 \), and adding this to \( 0 \le r' \lt b \) gives \( -b \lt r' - r \lt b \). Dividing by \( |b| \gt 0 \) then preserves the strict inequality. B

\( q - q' \) is an integer with \( |q-q'| \lt 1 \), so \( q - q' = 0 \), i.e. \( q = q' \); then \( r = a - bq = a - bq' = r' \). Uniqueness is proved.

This is the only place discreteness is used in the uniqueness half: there is no integer strictly between \( -1 \) and \( 1 \) other than \( 0 \). Over \( \mathbb{Q} \) the same computation gives \( |q-q'| \lt 1 \) and stops there, which is exactly why uniqueness fails in a field. B

Now let \( b \lt 0 \), so \( |b| = -b \gt 0 \). Apply Steps 1–7 to the pair \( (a, |b|) \): there are unique \( q_0, r \) with \( a = |b| q_0 + r \) and \( 0 \le r \lt |b| \). Since \( |b| = -b \), \[ a \;=\; (-b) q_0 + r \;=\; b(-q_0) + r , \] so \( (q, r) = (-q_0, r) \) satisfies the conclusion for \( b \).

A pure change of variable: the remainder is untouched and only the sign of the quotient flips. Uniqueness transfers because \( q \mapsto -q \) is a bijection of \( \mathbb{Z} \), so distinct solutions for \( b \) would give distinct solutions for \( |b| \). This is why the bound is stated as \( r \lt |b| \) and not \( r \lt b \). A

Closed form for \( q \). For \( b \gt 0 \), divide \( 0 \le a - bq \lt b \) by \( b \): \[ 0 \le \frac{a}{b} - q \lt 1 \quad\Longleftrightarrow\quad q \le \frac{a}{b} \lt q+1 \quad\Longleftrightarrow\quad q = \Big\lfloor \frac{a}{b} \Big\rfloor . \] For \( b \lt 0 \), Step 8 gives \( q = -\lfloor a/|b| \rfloor = -\lfloor -a/b \rfloor = \lceil a/b \rceil \).

Dividing by \( b \gt 0 \) preserves both inequalities; the middle statement is precisely the defining property of the floor function, \( \lfloor x \rfloor \) being the unique integer \( n \) with \( n \le x \lt n+1 \). The last equality uses the identity \( \lceil x \rceil = -\lfloor -x \rfloor \), valid for all real \( x \). \( \blacksquare \) C

Result

\[ \forall a \in \mathbb{Z},\ \forall b \in \mathbb{Z}\setminus\{0\} \ \ \exists!\,(q,r) \in \mathbb{Z}^2 : \quad a = bq + r, \quad 0 \le r \lt |b| \]

Reading. Quotient and remainder are not chosen, they are forced. Given the dividend, the divisor and the convention \( 0 \le r \lt |b| \), there is exactly one way to split \( a \) into “a whole number of copies of \( b \)” plus “what is left over”, and the leftover is always non-negative and always strictly smaller in size than the divisor.

Scope. All \( a \in \mathbb{Z} \), including negative \( a \), and all \( b \neq 0 \), including negative \( b \). The remainder never inherits the sign of \( a \) or of \( b \). The statement is false in every field, meaningless for \( b = 0 \), and generalises verbatim to any Euclidean domain once \( |\cdot| \) is replaced by that domain's Euclidean function — \( \deg \) in \( F[t] \), the norm \( N(x+iy) = x^2+y^2 \) in \( \mathbb{Z}[i] \) — though uniqueness of \( (q,r) \) is special to \( \mathbb{Z} \) and \( F[t] \) and fails in \( \mathbb{Z}[i] \).

Corollaries & converses

Divisibility test. \( b \mid a \) if and only if \( r = 0 \). (If \( r = 0 \) then \( a = bq \); conversely if \( a = bc \) then \( (c, 0) \) is an admissible pair, and uniqueness forces \( r = 0 \).) This turns a quantified statement, “\( \exists c: a = bc \)”, into a finite computation.
Residue classes. For \( n \ge 1 \) every integer is congruent modulo \( n \) to exactly one of \( 0, 1, \ldots, n-1 \), so \( \mathbb{Z}/n\mathbb{Z} \) has exactly \( n \) elements and \( \{0,\ldots,n-1\} \) is a complete residue system. Existence gives “at least one”, uniqueness gives “at most one”.
The Euclidean algorithm. \( \gcd(a,b) = \gcd(b,r) \) whenever \( a = bq+r \), because the pairs \( (a,b) \) and \( (b,r) \) have identical sets of common divisors. Iterating produces a strictly decreasing sequence of non-negative remainders, which must terminate; the last non-zero remainder is \( \gcd(a,b) \). See the Euclidean algorithm and Bézout's identity.
Base-\( \beta \) representation. For \( \beta \ge 2 \), every \( n \in \mathbb{Z}_{\gt 0} \) has a unique expansion \( n = \sum_{i=0}^{k} d_i \beta^i \) with \( 0 \le d_i \lt \beta \) and \( d_k \neq 0 \): apply the theorem to \( n \) and \( \beta \) to obtain \( d_0 \), then recurse on the quotient. Termination is the strict decrease of the quotients; uniqueness of the digits is uniqueness of the remainders.
\( \mathbb{Z} \) is a principal ideal domain. If \( I \subseteq \mathbb{Z} \) is a non-zero ideal, let \( b \) be its least positive element; for any \( a \in I \), writing \( a = bq + r \) puts \( r = a - bq \in I \) with \( 0 \le r \lt b \), so \( r = 0 \) by minimality and \( I = b\mathbb{Z} \). Every use of the division algorithm in this argument is the descent of Step 4.
Converse (characterisation of the quotient). If \( a = bq + r \) with \( 0 \le r \lt |b| \), then necessarily \( q = \lfloor a/b \rfloor \) for \( b \gt 0 \). So the converse direction holds and is useful: verifying the two conditions certifies that a guessed pair is the quotient and remainder, with no further computation.
Converse that fails. “Any \( (q,r) \) with \( a = bq+r \) and \( |r| \lt |b| \) is the pair delivered by the theorem” is false: \( -17 = 5(-3) + (-2) \) satisfies \( |-2| \lt 5 \) but the theorem's pair is \( (-4, 3) \). The one-sided bound \( r \ge 0 \) is indispensable.

Fails without

Divisor zero (\( b = 0 \)): the admissible range \( 0 \le r \lt 0 \) is empty, so no pair exists for any \( a \) whatsoever — not even for \( a = 0 \). This is not a boundary case that can be patched by a convention; the statement has no content when \( b = 0 \), which is why every implementation must trap it separately. Machine arithmetic reflects this: integer division by zero is undefined behaviour in C and raises ZeroDivisionError in Python, rather than returning a value.
Remainder range dropped: with only \( a = bq + r \) required, the solution set is infinite — \( 100 = 7\cdot 14 + 2 = 7\cdot 13 + 9 = 7\cdot 0 + 100 \) — and “the remainder of \( 100 \) on division by \( 7 \)” is not a well-defined number. Uniqueness is a property of the constraint, not of the equation.
Ambient ring is a field (\( \mathbb{Q}, \mathbb{R}, \mathbb{C} \)): take \( a = 1 \), \( b = 2 \) in \( \mathbb{Q} \). Both \( (q,r) = (0,1) \) and \( (q,r) = (\tfrac12, 0) \) satisfy \( a = bq+r \) with \( 0 \le r \lt 2 \), so uniqueness fails. Step 7 is the point of failure: \( |q - q'| = \tfrac12 \lt 1 \) no longer forces \( q = q' \) once \( q \) may be non-integral. Equivalently, in a field every non-zero element divides every element, so “remainder” carries no information.
Leading coefficient not invertible (\( \mathbb{Z}[t] \)): the polynomial analogue with \( \deg \) in place of \( |\cdot| \) needs the divisor's leading coefficient to be a unit. In \( \mathbb{Z}[t] \) take \( a = t \) and \( b = 2 \), with \( \deg 2 = 0 \): we would need \( t = 2q(t) + r \) with \( r = 0 \) or \( \deg r \lt 0 \), i.e. \( t = 2q(t) \), which is impossible since \( 2 \nmid 1 \) in \( \mathbb{Z} \). Over \( \mathbb{Q}[t] \) the same division succeeds with \( q = \tfrac12 t \). The theorem is a statement about \( F[t] \) for \( F \) a field, not about polynomials in general.
Well-ordering dropped: Step 3 needs the candidate set to attain its lower bound, which is well-ordering and not merely boundedness. Run the same argument in an ordered ring whose non-negative part is not well-ordered — \( \mathbb{Z}[x] \), ordered by leading coefficient, so that \( x \) exceeds every integer — with \( a = x \) and \( b = 2 \). Every candidate \( x - 2k \), \( k \in \mathbb{Z} \), is positive, and \( x - 2(k+1) \lt x - 2k \), so the candidate set is non-empty and bounded below by \( 0 \) yet has no least element: Step 3 has nothing to select. And no remainder exists, as it must not — \( x = 2q + r \) with \( r \in \{0,1\} \) would force \( 2 \mid 1 \) among the coefficients. Existence in this proof is entirely an application of well-ordering; no other principle is used.

Common errors

“\( -17 \div 5 \) gives \( q = -3 \), \( r = -2 \).” That is truncation toward zero, which is what C, C++, Java, Go and Rust compute for -17 / 5 and -17 % 5. It is not the theorem's pair, because \( -2 \lt 0 \) violates \( r \ge 0 \). The theorem gives \( q = \lfloor -3.4 \rfloor = -4 \) and \( r = -17 - 5(-4) = 3 \). Python's // and % implement the floored convention and return \( -4 \) and \( 3 \).
“\( 0 \le r \le |b| \).” The value \( r = |b| \) is never attained and admitting it destroys uniqueness at once: \( 10 = 5\cdot 1 + 5 = 5\cdot 2 + 0 \) would both be legal. The half-open interval is exactly \( |b| \) integers wide, which is the whole point.
“For \( b \lt 0 \) the remainder is negative.” It is not: the bound is \( 0 \le r \lt |b| \) for every non-zero \( b \). Dividing \( -1387 \) by \( -360 \) gives \( q = 4 \) and \( r = 53 \), not \( r = -53 \). The remainder is a function of \( a \) and \( |b| \) alone.
“\( q \) is \( a/b \) rounded to the nearest integer.” Rounding to nearest gives the balanced remainder of Problem 5, in the range \( (-|b|/2, |b|/2] \), not the standard one — and then only if ties are broken downward, since rounding \( a/b = 1/2 \) up would return \( r^{*} = -|b|/2 \), the excluded endpoint. For \( a = 9, b = 5 \) rounding gives \( q = 2, r = -1 \); the theorem gives \( q = 1, r = 4 \).
Invoking well-ordering without checking \( S \neq \emptyset \). Step 2 is not a formality. A proof that writes “let \( r \) be the least non-negative value of \( a - bk \)” and moves on has assumed the conclusion for negative \( a \), where the witness genuinely has to be constructed.
Calling it an algorithm. The proof given here is non-constructive in flavour — it takes a minimum of an infinite set — and produces no procedure. The Euclidean algorithm is an algorithm; this is the theorem that makes it terminate.
Proving existence and forgetting uniqueness. The applications that matter most (residue systems, base-\( \beta \) digits, well-definedness of \( a \bmod n \)) turn on the uniqueness half: existence alone gives “some remainder”, never “the remainder”. A proof that stops at Step 4 has proved the less useful half.

Discussion

The result is old enough that its statement predates the vocabulary used to state it. Euclid's Elements, Book VII, Propositions 1 and 2, describes repeated subtraction of the lesser magnitude from the greater — anthyphairesis — and treats the process as evidently terminating for numbers; the modern formulation with a quantified pair \( (q,r) \) and an explicit remainder range is a nineteenth-century tidying, contemporaneous with the axiomatisation of \( \mathbb{N} \) by Dedekind and Peano that supplies the well-ordering the proof needs. What the ancients treated as a self-evident feature of magnitudes is now isolated as the one non-trivial input.

Two features of the proof are worth separating. Existence is a descent argument and is genuinely about order: the set of candidate remainders is non-empty and bounded below, and its minimum cannot be as large as \( |b| \) because one more subtraction would beat it. Uniqueness is arithmetic and is about discreteness: two admissible remainders differ by less than \( |b| \) and by a multiple of \( b \), so they do not differ at all. The two halves fail in different places, which is why the counterexamples above split into “no remainder exists” (\( b = 0 \), or \( \mathbb{Q}_{\ge 0} \) with no minimum) and “too many remainders exist” (a field, or a dropped range constraint).

The generalisation is the concept of a Euclidean domain: an integral domain \( R \) with a function \( \nu: R \setminus\{0\} \to \mathbb{Z}_{\ge 0} \) such that for all \( a \in R \) and \( b \neq 0 \) there are \( q, r \) with \( a = bq+r \) and either \( r = 0 \) or \( \nu(r) \lt \nu(b) \). Taking \( \nu = |\cdot| \) recovers this theorem; \( \nu = \deg \) gives polynomial long division over a field; \( \nu(x+iy) = x^2+y^2 \) gives division in the Gaussian integers \( \mathbb{Z}[i] \). Note what the general definition drops: uniqueness. In \( \mathbb{Z}[i] \), dividing \( 3+4i \) by \( 2 \) admits several remainders of norm less than \( N(2) = 4 \), and no canonical choice is singled out. Uniqueness is a luxury of the totally ordered case, and the Euclidean algorithm does not need it — only the strict decrease of \( \nu \) matters for termination. Every Euclidean domain is a principal ideal domain by the argument in the Corollaries, and hence a unique factorisation domain; the converses both fail, \( \mathbb{Z}\big[\tfrac{1+\sqrt{-19}}{2}\big] \) being the standard example of a principal ideal domain that is not Euclidean.

The choice of remainder range is a genuine design decision with consequences, and computing has had to make it explicitly. Three conventions are in use for \( a = bq + r \): floored division, \( q = \lfloor a/b \rfloor \), giving \( r \) the sign of \( b \) — the convention of this theorem when \( b \gt 0 \), and the one implemented by Python's // and %; truncated division, \( q \) rounded toward zero, giving \( r \) the sign of \( a \) — the convention mandated by C99 and inherited by most of its descendants; and Euclidean division, \( 0 \le r \lt |b| \) for both signs of \( b \), which is the theorem exactly as stated here. Knuth argues in The Art of Computer Programming for the floored convention on the grounds that it makes \( r \) a periodic function of \( a \) with period \( b \), so that \( a \bmod b \) is compatible with congruence; the truncated convention breaks that periodicity at \( a = 0 \). Ada exposes both, as mod (floored) and rem (truncated). For \( b \gt 0 \) — the case that arises in number theory — floored and Euclidean coincide, which is why the distinction rarely surfaces in mathematics and constantly surfaces in code.

Common misconceptions. (i) That the theorem asserts something about the decimal expansion of \( a/b \) — it does not; it is a statement in \( \mathbb{Z} \) that mentions no rational number, and the closed form \( q = \lfloor a/b\rfloor \) is a corollary derived after the fact in Step 9. (ii) That the divisor must be smaller than the dividend — nothing of the kind is assumed; \( 3 = 100\cdot 0 + 3 \) is the correct division of \( 3 \) by \( 100 \), with \( q = 0 \). (iii) That “the remainder” is a property of \( a \) and \( b \) independent of the convention — it is a property of \( a \), \( b \), and the chosen interval of length \( |b| \); the theorem fixes that interval to be \( [0,|b|) \), and the balanced convention of Problem 5 is an equally valid theorem with a different answer.

Worked examples

Example 1. A spacecraft mission clock reports an elapsed time of \( 100\,000 \) seconds since launch. Express this as days, hours, minutes and seconds, and justify each step by the division algorithm.

Write \( T = 100\,000\ \mathrm{s} \). One day is \( 86\,400\ \mathrm{s} \), one hour \( 3600\ \mathrm{s} \), one minute \( 60\ \mathrm{s} \). Divide \( T \) by \( 86\,400 \): \[ 100\,000 = 86\,400 \cdot 1 + 13\,600, \qquad 0 \le 13\,600 \lt 86\,400 . \]

The theorem with \( a = 100\,000 \), \( b = 86\,400 \gt 0 \) guarantees exactly one such pair; the check \( 0 \le 13\,600 \lt 86\,400 \) certifies that \( (q,r) = (1, 13\,600) \) is the pair, by the converse corollary. So the elapsed time is \( 1 \) day plus \( 13\,600\ \mathrm{s} \). A

Divide the remainder by \( 3600 \): \[ 13\,600 = 3600 \cdot 3 + 2800, \qquad 0 \le 2800 \lt 3600 . \]

A fresh application of the theorem to \( a = 13\,600 \), \( b = 3600 \). Because \( 3600 \mid 86\,400 \), the hours digit obtained this way agrees with the one obtained by dividing \( T \) directly by \( 3600 \) and reducing modulo \( 24 \); the recursion is the base-conversion corollary in mixed radix \( (24, 60, 60) \). B

Divide again by \( 60 \): \[ 2800 = 60 \cdot 46 + 40, \qquad 0 \le 40 \lt 60 . \]

Third application, with \( a = 2800 \), \( b = 60 \). The remainders terminate here because \( 40 \lt 60 \) is already the seconds field. A

Reassemble and verify: \[ 1\cdot 86\,400 + 3\cdot 3600 + 46 \cdot 60 + 40 \;=\; 86\,400 + 10\,800 + 2760 + 40 \;=\; 100\,000 . \]

The check is not optional bookkeeping: it confirms the arithmetic, and uniqueness then guarantees no other set of digits in the ranges \( 0 \le h \lt 24 \), \( 0 \le m \lt 60 \), \( 0 \le s \lt 60 \) represents the same time. A

\[ 100\,000\ \mathrm{s} \;=\; 1\ \mathrm{d}\ \ 3\ \mathrm{h}\ \ 46\ \mathrm{min}\ \ 40\ \mathrm{s} \]

Reading. Mixed-radix time notation is the division algorithm applied three times, each application supplying one field. Every digit lies in its stated range because the theorem forces \( 0 \le r \lt |b| \), and the representation is unique for the same reason.

Scope. Exact for any non-negative integer number of seconds. For a negative elapsed time (a count-down clock reading \( T \lt 0 \)) the same three divisions apply unchanged and still return non-negative fields, but the day count becomes negative — see Example 2.

Example 2. An inertial platform integrates its yaw rate and reports a cumulative heading of \( -1387^{\circ} \). Reduce this to a compass heading in \( [0^{\circ}, 360^{\circ}) \). Then repeat the reduction with the divisor \( b = -360 \), as would arise from a sensor that counts clockwise turns as negative, and confirm the closed forms of Step 9.

Take \( a = -1387 \) and \( b = 360 \gt 0 \). By Step 9, \( q = \lfloor a/b \rfloor \): \[ \frac{-1387}{360} = -3.85277\ldots, \qquad q = \lfloor -3.85277\ldots \rfloor = -4 . \]

The floor of a negative non-integer is the next integer down, not the truncation: \( -4 \le -3.8527\ldots \lt -3 \). Truncating would give \( -3 \) and is the single commonest error in this calculation. B

Recover the remainder from the defining equation, \( r = a - bq \): \[ r = a - bq = -1387 - 360\cdot(-4) = -1387 + 1440 = 53 . \]

Never compute \( r \) by a separate rounding — derive it from the defining equation, so that \( a = bq + r \) holds identically. A

Check admissibility: \( 0 \le 53 \lt 360 \). Hence \( (q,r) = (-4, 53) \) and \[ -1387 = 360\cdot(-4) + 53 . \]

Existence plus the converse corollary: a pair satisfying both conditions is the pair, so no further verification is needed. Contrast the truncated convention, which returns \( q = -3, r = -307 \) — a valid equation, \( -1080 - 307 = -1387 \), but an inadmissible remainder. A

Now \( b = -360 \lt 0 \). By Step 8 the remainder is unchanged and the quotient flips sign; equivalently, by Step 9, \( q = \lceil a/b \rceil \): \[ \frac{-1387}{-360} = 3.85277\ldots, \qquad q = \lceil 3.85277\ldots \rceil = 4, \qquad r = -1387 - (-360)(4) = -1387 + 1440 = 53 . \]

The two routes agree, as they must: Step 8 gives \( q = -q_0 = -(-4) = 4 \). Note \( 0 \le 53 \lt |{-360}| = 360 \), so the remainder is again non-negative — the sign of the divisor never reaches the remainder. B

Interpretation: \( -1387^{\circ} \equiv 53^{\circ} \pmod{360^{\circ}} \), and the quotient counts complete revolutions — four full turns clockwise, leaving the platform pointing \( 53^{\circ} \) east of north.

The remainder is the physically meaningful quantity (the heading); the quotient is the winding number, which a heading indicator discards but a cable-wrap monitor must keep. Both are outputs of the same theorem, and it is uniqueness that makes “the heading” well defined. C

\[ -1387^{\circ} = 360^{\circ}\cdot(-4) + 53^{\circ} = (-360^{\circ})\cdot 4 + 53^{\circ}, \qquad \text{heading} = 53^{\circ} \]

Reading. The remainder \( 53^{\circ} \) is the same for \( b = +360^{\circ} \) and \( b = -360^{\circ} \); only the sign of the revolution count changes. A negative dividend does not produce a negative remainder.

Scope. Exact for integer degrees. For a real-valued heading the same reduction is \( \theta - 360^{\circ}\lfloor \theta/360^{\circ}\rfloor \), which is the floored convention extended to \( \mathbb{R} \); it is a definition there, not a theorem, since uniqueness of \( (q,r) \) over \( \mathbb{R} \) requires \( q \) to be constrained to \( \mathbb{Z} \) by fiat.

Problems

Find the quotient and remainder of \( a = 2026 \) on division by \( b = 45 \), and verify both conditions of the theorem.
Solution

Estimate \( q \) by Step 9: \( 2026/45 = 45.0\overline{2} \), so \( q = \lfloor 45.02\ldots \rfloor = 45 \). Then \( r = a - bq = 2026 - 45\cdot 45 = 2026 - 2025 = 1 \). Both conditions hold: \( 45\cdot 45 + 1 = 2026 \), and \( 0 \le 1 \lt 45 \). By uniqueness, \( (q,r) = (45,1) \) and no other pair works. Incidentally \( r \neq 0 \), so \( 45 \nmid 2026 \).
Repeat the previous problem for \( a = -2026 \) with \( b = 45 \), and then with \( b = -45 \). State the remainder in each case.
Solution

For \( b = 45 \): \( -2026/45 = -45.02\overline{2} \), so \( q = \lfloor -45.02\ldots\rfloor = -46 \) (not \( -45 \): the floor of a negative non-integer goes down). Then \( r = -2026 - 45(-46) = -2026 + 2070 = 44 \), and \( 0 \le 44 \lt 45 \). So \( -2026 = 45\cdot(-46) + 44 \).

For \( b = -45 \): by Step 8 the remainder is unchanged and the quotient flips, giving \( q = 46 \), \( r = 44 \). Check: \( (-45)(46) + 44 = -2070 + 44 = -2026 \), and \( 0 \le 44 \lt |-45| = 45 \). Equivalently \( q = \lceil -2026/-45 \rceil = \lceil 45.02\ldots\rceil = 46 \).

The remainder is \( 44 \) in both cases. Note the contrast with Problem 1: negating the dividend does not negate the remainder; \( 1 \) becomes \( 44 = 45 - 1 \).
Show that \( n^2 \equiv 0 \) or \( 1 \pmod 4 \) for every \( n \in \mathbb{Z} \), and deduce that no integer of the form \( 4k+3 \) is a sum of two squares. Illustrate with \( 2027 \).
Solution

By the division algorithm with \( b = 2 \), every \( n \) is uniquely \( n = 2q + r \) with \( r \in \{0,1\} \) — existence gives the two cases, uniqueness guarantees they are exhaustive and disjoint. If \( r = 0 \) then \( n^2 = 4q^2 \equiv 0 \pmod 4 \). If \( r = 1 \) then \( n^2 = 4q^2 + 4q + 1 = 4(q^2+q) + 1 \equiv 1 \pmod 4 \). So \( n^2 \bmod 4 \in \{0,1\} \).

Hence for any \( m, n \), the sum \( m^2 + n^2 \) is congruent mod \( 4 \) to one of \( 0+0 = 0 \), \( 0+1 = 1 \), \( 1+1 = 2 \) — never \( 3 \). Any integer of the form \( 4k+3 \) is therefore not a sum of two integer squares.

Illustration: \( 2027 = 4\cdot 506 + 3 \) (since \( 4\cdot 506 = 2024 \) and \( 0 \le 3 \lt 4 \)), so \( 2027 \) is not a sum of two squares. Checking by hand would require testing \( m \le \lfloor\sqrt{2027}\rfloor = 45 \); the congruence settles it in one division.
Prove the closed forms of Step 9 directly from the theorem: if \( a = bq+r \) with \( 0 \le r \lt |b| \), then \( q = \lfloor a/b\rfloor \) when \( b \gt 0 \) and \( q = \lceil a/b\rceil \) when \( b \lt 0 \). Verify both with \( a = -1387 \), \( |b| = 360 \).
Solution

Let \( b \gt 0 \). From \( a = bq + r \) we get \( a - bq = r \), and the hypothesis \( 0 \le r \lt b \) becomes \( 0 \le a - bq \lt b \). Dividing by \( b \gt 0 \) preserves both inequalities: \( 0 \le a/b - q \lt 1 \), i.e. \( q \le a/b \lt q+1 \). Since \( q \in \mathbb{Z} \), this is exactly the defining property of the floor, so \( q = \lfloor a/b\rfloor \).

Let \( b \lt 0 \), so \( |b| = -b \). The hypothesis reads \( 0 \le a - bq \lt -b \). Dividing by \( b \lt 0 \) reverses both inequalities: \( 0 \ge a/b - q \gt -1 \), i.e. \( q - 1 \lt a/b \le q \). Since \( q \in \mathbb{Z} \), that is the defining property of the ceiling, so \( q = \lceil a/b\rceil \).

Check with \( a = -1387 \). For \( b = 360 \): \( a/b = -3.8527\ldots \), \( \lfloor a/b\rfloor = -4 \), and indeed \( -1387 = 360(-4) + 53 \) with \( 0 \le 53 \lt 360 \). For \( b = -360 \): \( a/b = 3.8527\ldots \), \( \lceil a/b \rceil = 4 \), and \( -1387 = (-360)(4) + 53 \) with \( 0 \le 53 \lt 360 \). Both closed forms return the quotients found in Example 2.
(Balanced, or least-absolute, remainders.) Let \( b \gt 0 \). Prove that for every \( a \in \mathbb{Z} \) there are unique \( q^{*}, r^{*} \in \mathbb{Z} \) with \( a = bq^{*} + r^{*} \) and \( -b/2 \lt r^{*} \le b/2 \). Compute \( (q^{*}, r^{*}) \) for \( a = 95, b = 8 \) and for \( a = 100, b = 8 \), and compare with the standard pair.
Solution

Existence. Apply the theorem to get \( a = bq + r \) with \( 0 \le r \lt b \). If \( r \le b/2 \), set \( (q^{*}, r^{*}) = (q, r) \); then \( r^{*} \ge 0 \gt -b/2 \), so the range holds. If \( r \gt b/2 \), set \( (q^{*}, r^{*}) = (q+1,\ r-b) \); then \( a = b(q+1) + (r-b) \) still holds identically, and \( r \gt b/2 \) gives \( r^{*} = r-b \gt -b/2 \) while \( r \lt b \) gives \( r^{*} \lt 0 \le b/2 \). Either way the range \( -b/2 \lt r^{*} \le b/2 \) is met.

Uniqueness. The half-open interval \( (-b/2,\ b/2] \) has length exactly \( b \), so it contains exactly \( b \) integers (for \( b \) even, \( -b/2+1, \ldots, b/2 \); for \( b \) odd, \( -(b-1)/2, \ldots, (b-1)/2 \) — in both cases \( b \) values). If \( bq_1 + r_1 = bq_2 + r_2 \) with both remainders in that interval, then \( b(q_1-q_2) = r_2-r_1 \) and \( |r_2 - r_1| \lt b \) because two points of an interval of length \( b \) differ by less than \( b \) — strictly, since one endpoint is excluded. Hence \( b|q_1-q_2| \lt b \), so \( |q_1-q_2| \lt 1 \), so \( q_1 = q_2 \) and then \( r_1 = r_2 \). This is Steps 5–7 verbatim with the interval shifted.

Numbers. For \( a = 95, b = 8 \): standard division gives \( 95 = 8\cdot 11 + 7 \), and \( 7 \gt 8/2 = 4 \), so shift: \( q^{*} = 12 \), \( r^{*} = 7 - 8 = -1 \). Check \( 8\cdot 12 - 1 = 95 \) and \( -4 \lt -1 \le 4 \). For \( a = 100, b = 8 \): \( 100 = 8\cdot 12 + 4 \), and \( 4 \le 8/2 = 4 \), so no shift is needed: \( (q^{*}, r^{*}) = (12, 4) \). The boundary case \( r = b/2 \) is kept, not shifted — that is precisely the choice that makes the interval half-open on the correct side and preserves uniqueness.