Back to the on-screen lesson ·
The division algorithm and the uniqueness that makes the remainder well defined, divisibility as an equation to unfold, and the primes every integer is built from in exactly one way.
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 the division algorithm with the range its remainder must lie in, compute quotients and remainders, and prove statements about divisibility by unfolding each one into an equation and folding the definition back up at the end. You will also be able to test a number for primality by dividing only up to its square root, say why that is enough, count the divisors of a number from its factorisation, and say why the fundamental theorem is the reason one is not counted as prime.
Lesson 6 proved that divisibility is transitive by unfolding its definition, and lesson 13 found it to be a partial order. Lesson 8 used the primes in Euclid's contradiction. This unit goes back and lays the foundation all of that was standing on, which is one theorem about division with remainder.
$a \mid b$ means $b = ak$ for some integer $k$ — $a$ divides $b$, with no remainder and no fraction anywhere in the definition. A prime is an integer above $1$ whose only positive divisors are $1$ and itself; anything else above $1$ is composite. The quotient and remainder of $a$ by $b$ are the $q$ and $r$ with $a = bq + r$ and $0 \le r < b$.
The division algorithm. For integers $a$ and $b > 0$ there are unique integers $q$ and $r$ with $$a = bq + r, \qquad 0 \le r < b.$$
It is called an algorithm and it is a theorem, and the word that earns its keep is unique. Existence is obvious enough — take away copies of $b$ until you cannot — and uniqueness is what lets the remainder be spoken of as the remainder, which is what the next two lessons need.
Uniqueness has a one-line proof worth seeing. If $a = bq + r = bq' + r'$ with both remainders in range, then $b(q - q') = r' - r$, so $b$ divides $r' - r$. But $|r' - r| < b$, and the only multiple of $b$ smaller than $b$ in size is zero. So $r = r'$, and then $q = q'$.
Divisibility. $a \mid b$ means $b = ak$ for an integer $k$. Written that way it is an equation you can substitute into, and every proof about divisibility starts by writing it: if $a \mid b$ and $a \mid c$ then $b = ak$ and $c = a\ell$, so $b + c = a(k + \ell)$, so $a \mid b + c$. Three lines, and the whole content was unfolding the definition.
The fundamental theorem of arithmetic. Every integer above $1$ is a product of primes, in exactly one way apart from the order. Existence is a strong induction: either $n$ is prime, or $n = ab$ with both factors smaller, and the hypothesis applies to each. Uniqueness is harder and needs Euclid's lemma — if a prime divides a product it divides one of the factors — which the next lesson proves from Bézout's identity.
From unique factorisation everything else falls out: the divisor count, the greatest common divisor read off prime by prime, and the reason $1$ is not called prime — if it were, every number would have infinitely many factorisations.
Another way: steps
To prove something about divisibility:
Another way: example
How many divisors has $60 = 2^2 \cdot 3 \cdot 5$? A divisor chooses a power of $2$ from $\{0, 1, 2\}$, of $3$ from $\{0, 1\}$ and of $5$ from $\{0, 1\}$, independently: $3 \times 2 \times 2 = 12$. The product rule of unit 4, applied to exponents.
To test whether $n$ is prime, divide by the primes up to $\sqrt{n}$ and stop. The reason is a short argument rather than a convention: if $n = ab$ with $1 < a \le b$, then $a^2 \le ab = n$, so $a \le \sqrt{n}$. Any composite number therefore has a factor at or below its square root, and finding none means there is none.
That turns testing $91$ into four divisions — by $2$, $3$, $5$ and $7$ — and the fourth succeeds: $91 = 7 \times 13$. Numbers like $91$ and $51$ are worth meeting, because they survive the checks people do by eye and are composite anyway.
$1$ is not prime, and the reason is uniqueness rather than taste. If it were, $12$ would factor as $2^2 \cdot 3$ and as $1 \cdot 2^2 \cdot 3$ and as $1^5 \cdot 2^2 \cdot 3$, and the fundamental theorem would be false as stated. Definitions are chosen to make theorems true, and this is the clearest small example of it in the course.
Writing $a \mid b$ as $a/b$. Divisibility is a statement, not a number, and the notation runs the other way from division: $2 \mid 6$ and $2/6$ is a third.
Forgetting $0 \le r$. The remainder is never negative under this convention, so $-7$ divided by $3$ is $-3$ remainder $2$, not $-2$ remainder $-1$.
Testing primality past the square root. Correct and wasteful.
Assuming unique factorisation is obvious. It is a theorem, it fails in other number systems that look similar, and the next lesson is what proves it.
$a \mid b$ is either true or false; it does not produce a number. That matters because the moment it is treated as division, fractions enter an argument that is about integers, and the conclusion stops being about integers too. The definition — $b = ak$ for some integer $k$ — keeps everything inside the integers, and unfolding it is the first move of every proof in this unit.
Claim: if $a \mid b$ then $a \mid bc$ for every integer $c$. Unfold: $b = ak$ for some integer $k$.
Turn the statement into an equation.
Then $bc = (ak)c = a(kc)$, and $kc$ is an integer.
Algebra on the equation.
So $bc$ is $a$ times an integer, which is the definition of $a \mid bc$. The whole proof was the definition, written down and folded back up.
Three lines, and no arithmetic.
$36 = 2^2 \cdot 3^2$. A divisor takes $2$ to the power $0$, $1$ or $2$, and $3$ to the power $0$, $1$ or $2$.
Say what one divisor is, as a sequence of choices.
The two choices are independent, so there are $3 \times 3 = 9$ divisors.
The product rule.
Listing them checks it: $1, 2, 3, 4, 6, 9, 12, 18, 36$. And the count works only because the factorisation is unique — otherwise a divisor could be described in two ways and would be counted twice.
The theorem underneath the arithmetic.
Unfold both: $b = ak$ and $c = a\ell$ for integers $k$ and $\ell$.
Two hypotheses, two equations, two fresh letters.
Then $3b - 2c = 3ak - 2a\ell = a(3k - 2\ell)$.
Factor out $a$.
And $3k - 2\ell$ is an integer, so $a$ divides $3b - 2c$. Notice that nothing about $3$ and $-2$ mattered: the same proof gives $a \mid (xb + yc)$ for any integers $x$ and $y$, and that combination is exactly what Bézout's identity in the next lesson is about.
Divide each number by $5$ and give the quotient and the remainder.
| Quotient | Remainder | |
|---|---|---|
| $16$ | ||
| $27$ | ||
| $38$ |
$128 = 2^7$. How many positive divisors does it have?
Answer:
Divide $11$ by $4$. What is the remainder?
Answer:
Match each number to its prime factorisation.
| $2^2 \cdot 3$ | $2^2 \cdot 3^2$ | $2^2 \cdot 3 \cdot 5$ | $2^2 \cdot 5^2$ | |
|---|---|---|---|---|
| $12$ | ||||
| $36$ | ||||
| $60$ | ||||
| $100$ |
Mark every prime in the list.
This task has no paper form; do it on a device.
Suppose the primes up to $3$ were all of them. Multiply them and add one to get $7$. What is its smallest prime factor?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Divide each number by $8$ and give the quotient and the remainder.
| Quotient | Remainder | |
|---|---|---|
| $25$ | ||
| $42$ | ||
| $59$ |
You can divide with remainder, prove a divisibility statement by unfolding the definition, and count divisors from a factorisation. Say in your own words why the uniqueness of the remainder matters and why testing stops at the square root. Next: the algorithm that finds a greatest common divisor without factorising anything.
10. Your turn: show that if $a \mid b$ and $a \mid c$ then $a \mid (3b - 2c)$, step 3