In grade 4 you wrote $17 \div 5 = 3$ R $2$. The division algorithm says the same thing as an equation, $17 = 5 \cdot 3 + 2$, and makes it work for every integer, negative ones included. Almost everything in this course leans on it: remainders, bases, the Euclidean algorithm and congruences.
Theorem (division algorithm). Let $a$ and $b$ be integers with $b > 0$. There are unique integers $q$ (the quotient) and $r$ (the remainder) with $$a = bq + r \quad\text{and}\quad 0 \le r < b.$$ In fact $q = \lfloor a/b \rfloor$, the largest integer that is at most $a/b$, and $r = a - bq$.
Why it works
Uniqueness. If also $a = bq' + r'$ with $0 \le r' < b$, then $b(q - q') = r' - r$. The right side is strictly between $-b$ and $b$, and the left side is a multiple of $b$, so both are $0$: $q = q'$ and $r = r'$.
Worked example: A positive dividend
- The largest multiple of $6$ that is at most $47$ is $6 \cdot 7 = 42$, so $q = 7$.
- $r = 47 - 42 = 5$, and $0 \le 5 < 6$.
Answer: $47 = 6 \cdot 7 + 5$.
Worked example: A negative dividend
- The multiples of $5$ near $-17$ are $-20$ and $-15$. We need the one at or below $-17$: $5 \cdot (-4) = -20$. So $q = -4$.
- $r = -17 - (-20) = 3$, and $0 \le 3 < 5$.
- Check: $5 \cdot (-4) + 3 = -20 + 3 = -17$.
Answer: $-17 = 5 \cdot (-4) + 3$, so $q = -4$ and $r = 3$.
Worked example: Counting backward on a calendar
- Going back 100 days is a change of $-100$ days. Divide by $7$: $-100 = 7 \cdot (-15) + 5$, since $7 \cdot (-15) = -105 \le -100$.
- The $15$ whole weeks change nothing, so going back 100 days lands on the same day as going forward $5$ days.
- Wednesday plus 5 days is Monday.
Answer: Monday.
Common mistake
-17 % 5 is -2; in Python it is 3. Mathematics always uses the remainder from $0$ to $b - 1$.Key idea