Twenty-three cookies, five friends. Hand them out one round at a time and the sharing stops cold: everyone gets 4 cookies, and 3 are left on the plate — not enough for a fifth round. Every child at the table would tell you the same thing without thinking twice.

That everyday act of sharing hides a small, exact piece of mathematics, one so familiar from primary-school remainders that it is easy to overlook how much rests on it. The division algorithm formalises exactly what just happened: for any two integers, there is one — and only one — sensible way to write "how many full rounds" and "how many are left over." Despite its name, it is not really an algorithm at all — it is a theorem guaranteeing that quotient and remainder always exist, and are unique.

It sounds almost too simple to deserve a name. But this one small guarantee is the load-bearing wall underneath an enormous amount of number theory. The Euclidean algorithm for finding the greatest common divisor is nothing more than this theorem applied again and again. The entire machinery of modular arithmetic — clock arithmetic, checksums, cryptography — is built on the remainder this theorem hands you. Get comfortable with quotient and remainder here, and a great deal of what follows in number theory turns out to be this same idea, dressed up in new clothes.

The statement

The condition 0 \le r < b is the whole point: it pins the remainder down to a single value. Without it you could write 23 = 5\cdot 3 + 8 or 23 = 5\cdot 2 + 13 and never agree on an answer — plenty of pairs satisfy a = bq+r on its own. Forcing r below b leaves only one choice, the one every child at the table already found: 23 = 5\cdot 4 + 3.

Notice the theorem asks for b to be positive. That's not fussiness — you can't share cookies among a negative number of friends, and "rows of b" only makes sense for a positive row length. The dividend a, on the other hand, is allowed to be any integer at all, including negative — worked example 2 below shows exactly what happens then.

Another view: hopping along the number line

Counters in rows is one picture; a number line gives another. Start at 0 and hop forward in steps of size b: 0, b, 2b, 3b, \dots. These hop-landing points are exactly the multiples of b. Now find where a sits. It will fall either exactly on a landing point, or somewhere in the gap just after one.

The quotient q counts how many hops it takes to reach the landing point at or just before a; the remainder r is the little bit of ground still left to walk from that landing point to reach a itself. Because each gap between landing points has length exactly b, that leftover bit can never be as long as a whole gap — which is precisely why r < b. Two pictures, one idea: rows of counters and hops on a line both cash out to the same a = bq + r.

Worked example 1 — back to the cookies

Lay the 23 cookies out in rows of 5. Step through the diagram: first the four complete rows appear (that's q = 4), then the short leftover row of three (that's r = 3) — too few to start a fifth row, exactly as r < b demands.

In general, laying out a counters into rows of b always finishes the same way: some number of full rows q, and a final row too short to complete, of size r.

The same picture works for any "pack into groups of a fixed size" story, not just cookies. Egg cartons hold 12 eggs; a minibus seats 15 passengers; a spreadsheet wraps text after 80 characters. Whatever the size of the group, the same two numbers appear every time: how many complete groups you can make (q), and how much is left stranded outside a complete group (r). The division algorithm is the single fact that guarantees this always works out to one tidy answer, never two.

Worked example 2 — when the dividend is negative

The theorem allows a to be negative too — and the rule 0 \le r < b still forces a non-negative remainder, which takes a moment's care. Divide -17 by 5.

A tempting first guess is q = -3, since 5\cdot(-3) = -15 is close to -17. But that leaves r = -17 - 5\cdot(-3) = -2 — negative, so it breaks the rule outright. The fix is to push the quotient one step further down, to q = -4:

Now the remainder lands safely inside [0, 5). So the quotient always rounds down (towards -\infty), never towards zero. This non-negative remainder is exactly what makes the whole theory of modular arithmetic run smoothly — a remainder is never allowed to be negative.

Worked example 3 — using it to test divisibility

When the remainder happens to land on 0, something special happens: a = bq exactly, with nothing left over. We say b divides a, written b \mid a. This is the relationship at the heart of everything that follows — factors and multiples are just another name for it.

Try it on two neighbours. Is 7 a divisor of 84? Run the division algorithm: 84 = 7\cdot 12 + 0 — remainder 0, so yes, 7 \mid 84. What about 85? 85 = 7\cdot 12 + 1 — remainder 1, not 0, so 7 does not divide 85. One extra cookie is all it takes to break a clean division.

The same check scales up beautifully. Is 1001 divisible by 7? Run it: 1001 = 7\cdot 143 + 0 — remainder 0, yes. In fact 1001 = 7\times 11\times 13, a small piece of number-theory folklore worth knowing: it's the reason the "divisibility by 7, 11 and 13" trick for big numbers works, and it's exactly the division algorithm, run three times, that confirms it.

Putting the three examples together

Step back and the three worked examples are really one idea wearing three hats. The cookies example shows the theorem in its most concrete form — physical objects, physical rows. The negative-number example shows the theorem still holding when the everyday intuition of "how many times does 5 go into it" gets slippery, and pins down exactly which convention to trust. The divisibility example shows what happens in the one special case, r = 0, that matters enough to earn its own name and its own symbol, b \mid a. Every later idea in this course — greatest common divisors, modular arithmetic, congruences — starts from one of these three moves: computing a remainder, handling its sign carefully, or asking whether it's zero.