More proofs in this course lean on divisibility than on any other single idea — "if n is even, then ___" shows up constantly starting in Chapter 4. This section fixes the definition precisely, gives it a symbol, and states the one fact that everything else here is built from: dividing any integer by a positive one always leaves a definite, predictable leftover.
Divides means "goes in evenly," with nothing left over. Think of splitting a pile of coins into equal smaller piles with none spare. When one number does not divide another, someone's pile comes up short. No matter how you split, at least one coin sits alone. This symbol is easy to flip by accident. Saying 3 divides 12 is true. Saying 12 divides 3 is false. The number on the left is always the one doing the dividing.
For integers a and b, say b divides a — written b \mid a — if there exists an integer k with a = bk. When b \mid a, a is a multiple of b and b is a factor (or divisor) of a. If no such k exists, write b \nmid a. An integer n is even if 2 \mid n and odd otherwise — equivalently, n = 2k+1 for some integer k. Note b \mid a is a statement (true or false, per §1), never a fraction: 3 \mid 12 is true; it does not mean \frac{3}{12}. Every integer divides 0 (take k = 0), and every integer is divided by 1 and by itself, so divisibility always has at least those trivial cases before asking whether anything more interesting holds. Parity — whether an integer is even or odd — is the simplest possible divisibility question, and it comes up constantly: every integer is one or the other, never both and never neither.
Theorem
The Division Algorithm
For any integer a and any positive integer b, there exist unique integers q (the quotient) and r (the remainder) such that a = bq + r, \qquad 0 \le r < b.
Existence. Consider the set of nonnegative integers of the form a - bk for integer k: \{\ldots, a-2b,\ a-b,\ a,\ a+b,\ a+2b,\ \ldots\} \cap \{0, 1, 2, \ldots\}. This set is nonempty — for k negative enough, a-bk grows without bound in the positive direction — so by the well-ordering principle it has a least element; call it r, achieved at some k=q, so r = a-bq, i.e. a = bq+r. If r \ge b, then r-b = a-b(q+1) \ge 0 would be a smaller nonnegative element of the same set, contradicting that r was least. So 0 \le r < b.
Uniqueness. Suppose a = bq_1+r_1 = bq_2+r_2 with both remainders in [0,b). Subtracting gives b(q_1-q_2) = r_2-r_1, so b divides r_2-r_1. But -b < r_2-r_1 < b, and the only multiple of b strictly between -b and b is 0, so r_1=r_2, which forces q_1=q_2 as well.
Quotient and remainder, live
Send a chip through -- f(x)=\lfloor x/4 \rfloor computes the quotient, g(x)=x-4\lfloor x/4\rfloor computes the remainder. Confirm every remainder that comes out is between 0 and 3.
Loading interactive…
Divides or does not divide
Sort each pair by whether the first number divides the second.
Loading interactive…
Recipe Apply the Division Algorithm Use when: you're given integers a and b, with b positive, and need the quotient q and remainder r satisfying a = bq + r Goal: the one pair of integers q and r with 0 \le r < b
-
1
Divide a by b to get a decimal, then round that decimal down toward negative infinity, never toward zero, to get the integer q.
Example
For a=-17, b=5: -17 \div 5 = -3.4. Round toward negative infinity, not toward zero, so q=-4, one step past -3.
- a is positive — rounding down and rounding toward zero land on the same integer, so ordinary division already gives q.
- a is negative and doesn't divide evenly — rounding down lands one integer further from zero than rounding toward zero would.
Why: only rounding down guarantees the remainder computed next lands in the required range 0 \le r < b.
-
2
Multiply b by the q from Step 1, then subtract that product from a to get r.
Example
Continuing with a=-17, b=5, q=-4: bq = 5(-4) = -20, so r = -17 - (-20) = 3.
Why: rearranging a=bq+r for r gives exactly this subtraction, the only value of r that keeps the equation true for this q.
-
3
Confirm the remainder from Step 2 is not negative and strictly less than b; if either check fails, q was rounded the wrong way.
Example
Here r=3, and 0 \le 3 < 5, so q=-4, r=3 passes. Rounding toward zero instead would give q=-3, and r = -17 - 5(-3) = -2, which fails the check since it's negative.
Why: this range is what makes q and r unique, exactly what the Division Algorithm guarantees.
Common mistakes
- Rounding a \div b toward zero instead of down when a is negative, producing a negative remainder.
- Skipping the check in Step 3 and accepting a remainder outside 0 \le r < b.
- Subtracting in the wrong order, computing bq - a instead of a - bq.
- Applying this recipe with a negative b, where the Division Algorithm as stated here doesn't apply.
Worked example
Find q and r for a = 47, b = 5
-
1
This runs Steps 1 through 3 of the recipe above; a is positive here, so rounding down and rounding toward zero agree. Write 47 = 5q + r with 0 \le r < 5.
-
2
Divide: 47 \div 5 = 9 with something left over — find the largest multiple of 5 not exceeding 47: 5 \times 9 = 45.
-
3
47 - 45 = 2, and 0 \le 2 < 5, so \boxed{47 = 5(9) + 2, \quad q=9,\ r=2} Check: 5 \times 9 + 2 = 45 + 2 = 47. ✓
Loading interactive…
Worked example
A negative dividend — the remainder is still non-negative
-
1
This is the exact case walked through in the recipe above, Steps 1 through 3, where the rounding direction actually matters. Write -17 = 5q + r with 0 \le r < 5.
-
2
A common trap: -17 \div 5 = -3.4, so guessing q=-3, r=-2 feels natural — but r=-2 violates 0 \le r < 5. The remainder is never negative.
-
3
Round q down instead (toward -\infty, not toward 0): q=-4 gives 5 \times (-4) = -20.
-
4
-17 - (-20) = 3, and 0 \le 3 < 5, so \boxed{-17 = 5(-4) + 3, \quad q=-4,\ r=3} Check: 5 \times (-4) + 3 = -20+3 = -17. ✓ The Division Algorithm's 0 \le r < b requirement is what rules out the tempting-but-wrong q=-3, r=-2.
Who uses this
Computer science
Every hashing scheme that spreads data across a fixed number of buckets —
a hash table, a load balancer routing requests across b servers — is
computing a remainder: key % b picks the bucket. The Division Algorithm
is the exact guarantee that makes this work at all: for any key and any
positive bucket count b, there is one and only one valid bucket index in
\{0, 1, \ldots, b-1\}, never a leftover that doesn't fit and never two
valid answers to choose between.
Check your understanding (counts toward your progress)
A student computes -17=5(-3)+(-2) and calls this the Division Algorithm's answer. What is wrong?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The Division Algorithm specifically requires 0\le r<b -- a negative remainder is never valid, even though a=bq+r holds arithmetically.
Using the Division Algorithm, find the remainder r for a=47, b=10 (so a=bq+r with 0\le r<b).
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Round q toward negative infinity: q=4, giving r=47-10(4)=7, which satisfies 0\le r<10.
Correct answer
Also accepted:
Why
Using the Division Algorithm's convention (remainder always non-negative), what is q when -23 = 4q+r with 0\le r<4?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Round q down (toward negative infinity): 4(-6)=-24, so r=-23-(-24)=1, giving -23=4(-6)+1 with a valid non-negative remainder.
Correct answer
Also accepted:
Why
Which integer is even by the definition n=2k?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
0=2(0), so 0 is even -- a common surprise, since 0 does not feel like a typical even number.