Back to the on-screen lesson ·
What one integer dividing another asserts, and the unique quotient and remainder that describe how the division fails.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state what $a \mid b$ asserts and prove the basic divisibility facts by substituting the equation the definition gives, find a counterexample to a divisibility claim that does not hold, state the division algorithm with the condition on the remainder that makes the quotient and remainder unique, and carry it out for positive and negative dividends.
Dividing $47$ by $6$ and answering 7 remainder 5 is arithmetic you have done since primary school. Number theory does one thing to it: it writes the answer as an equation, $47 = 6 \cdot 7 + 5$, and then never divides again.
That is not a notational preference. An equation between integers can be added, multiplied and substituted into; a quotient with a remainder trailing after it cannot. Every argument in this course that begins write $a = bq + r$ is using the equation, and the whole of the first unit is what that one rewriting makes possible.
$a \mid b$ is read $a$ divides $b$ and means there is an integer $c$ with $b = ac$. It is a statement, true or false — not an operation, and never a fraction: $3 \mid 12$ is true, and $12 \mid 3$ is false.
When $a \mid b$, $a$ is a divisor (or factor) of $b$ and $b$ is a multiple of $a$. A divisor of $b$ other than $b$ itself is proper.
In $a = bq + r$ the number $q$ is the quotient and $r$ the remainder. Two conventions to fix now: $d \mid 0$ holds for every $d$, since $0 = d \cdot 0$; and $0 \mid a$ holds only for $a = 0$.
Definition. For integers $a$ and $b$, $a \mid b$ when $b = ac$ for some integer $c$.
Three consequences follow straight from substituting that equation, and they are used constantly:
The last one is the reason searches for divisors terminate.
The division algorithm. For integers $a$ and $b$ with $b > 0$ there are unique integers $q$ and $r$ with $$a = bq + r, \qquad 0 \le r < b.$$
It is not an algorithm and it is a theorem, which the name obscures. What it says is that when $b$ does not divide $a$, the failure is still completely describable: there is exactly one way to write $a$ as a multiple of $b$ plus a small correction.
Existence comes from taking $q$ as large as possible with $bq \le a$; then $r = a - bq$ is at least $0$, and below $b$, or $q$ was not as large as possible. Uniqueness comes from subtracting two such expressions: if $bq_1 + r_1 = bq_2 + r_2$ then $b \mid (r_1 - r_2)$, and $|r_1 - r_2| < b$ forces $r_1 = r_2$, hence $q_1 = q_2$.
Another way: steps
Another way: example
$b = 7$, $a = 100$: the multiples of $7$ climb $\ldots, 91, 98, 105, \ldots$, and the largest at or below $100$ is $98 = 7 \cdot 14$. So $q = 14$, $r = 2$, and $100 = 7 \cdot 14 + 2$ with $0 \le 2 < 7$. Negative numbers obey the same rule and catch people out: $-100 = 7 \cdot (-15) + 5$, because the remainder must not be negative, so the quotient goes down rather than up.
Drop the requirement $0 \le r < b$ and the statement collapses into nothing: $100 = 7 \cdot 13 + 9$, $100 = 7 \cdot 12 + 16$, $100 = 7 \cdot 20 - 40$ are all true, and there are infinitely many more. What makes $q$ and $r$ the quotient and the remainder is one inequality.
So the theorem is best read as a normalisation result. Among infinitely many ways of writing $a$ in terms of $b$, exactly one is normal, and the normal form can be compared: two numbers leave the same remainder or they do not, and that question has a definite answer only because the remainder is pinned down.
Everything the rest of the course does with a modulus depends on that. When lesson 6 says two numbers are congruent modulo $n$, it will mean they have the same normal form under division by $n$ — and that is a well-defined relation exactly because this theorem says the normal form exists and is unique.
One more consequence is worth stating here. Because $r$ takes only the values $0, 1, \ldots, b - 1$, the integers fall into exactly $b$ classes under division by $b$. There are infinitely many integers and finitely many classes, so the pigeonhole principle applies to remainders, and a surprising number of arguments later in the course are pigeonhole arguments on remainders.
Reading $a \mid b$ as a division. The bar is not a slash. $a \mid b$ is a claim about existence of an integer; $a / b$ is a number. They even point opposite ways: $3 \mid 12$ is the true claim, and $3 / 12$ is the small fraction.
Splitting divisibility across a product. From $d \mid ab$ it does not follow that $d \mid a$ or $d \mid b$: $6 \mid 4 \cdot 3$ while $6$ divides neither. The statement becomes true when $d$ is prime, and that is a theorem (Euclid's lemma, lesson 4), not an observation. Using it for composite $d$ is the most common false step in an otherwise correct argument.
Treating a negative dividend loosely. The remainder is never negative. $-17$ divided by $5$ is $-4$ remainder $3$, not $-3$ remainder $-2$. Programming languages disagree with each other here; the theorem does not.
A fourth, quieter one: forgetting that $0$ is divisible by everything. It follows immediately from $0 = d \cdot 0$, and it matters, because it is what makes $d \mid (a - a)$ true and so makes congruence reflexive.
Claim: if $d \mid a$ and $d \mid b$ then $d \mid (5a - 3b)$. Write the hypotheses as equations: $a = dk$ and $b = dm$ for some integers $k$ and $m$.
The definition, turned into something you can substitute.
Then $5a - 3b = 5dk - 3dm = d(5k - 3m)$, and $5k - 3m$ is an integer.
One line of algebra.
So $d \mid (5a - 3b)$. Nothing about $5$ and $-3$ was used: any integer combination $ax + by$ of two multiples of $d$ is a multiple of $d$, and that single fact is what lesson 3 turns into Bézout's identity.
Generalise while it is free.
Divide $-59$ by $8$. The multiples of $8$ around $-59$ are $-64$ and $-56$; the largest one at or below $-59$ is $-64 = 8 \cdot (-8)$.
At or below, not nearest.
So $q = -8$ and $r = -59 - (-64) = 5$, giving $-59 = 8 \cdot (-8) + 5$ with $0 \le 5 < 8$.
The remainder came out positive, as it must.
The tempting answer $-59 = 8 \cdot (-7) - 3$ is a true equation and not the division algorithm's answer, because $-3$ is not in $[0, 8)$.
A true equation is not automatically the normal form.
Divide the first of them by $3$: one of $n = 3k$, $n = 3k + 1$, $n = 3k + 2$ holds, and exactly one, by the division algorithm.
Three cases, and the theorem says there are no others.
In the first case $3 \mid n$. In the second, $n + 2 = 3k + 3 = 3(k + 1)$. In the third, $n + 1 = 3k + 3$.
One of the three factors is a multiple of $3$ every time.
In each case one factor of the product is divisible by $3$, so the product is.
Divide each of these by $7$. Give the quotient and the remainder in every row.
| Quotient | Remainder | |
|---|---|---|
| $29$ | ||
| $59$ | ||
| $65$ |
Divide $57$ by $9$. What is the remainder?
Answer:
Mark the remainder of $27$ on division by $6$. The line runs from $0$ to $6$.
0 |——————————| 6
Mark the position with a cross, then write the value:
Does this hold for all integers: if $d \mid a$ then $d \mid ab$ for every integer $b$?
Write $154$ in the form $10q + r$ required by the division algorithm.
quotient a, remainder c
Put these four numbers in increasing order of the remainder each leaves on division by $12$.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Divide each of these by $6$. Give the quotient and the remainder in every row.
| Quotient | Remainder | |
|---|---|---|
| $21$ | ||
| $44$ | ||
| $52$ |
You can decide and prove divisibility claims, and divide any integer by a positive one in the unique normal form the division algorithm gives. Say in your own words why the condition $0 \le r < b$ is the whole content of that theorem. Next: turning repeated division into the fastest algorithm in the subject.
9. Your turn: show that the product of any three consecutive integers is divisible by $3$, step 3