Back to the on-screen lesson ·
The number and the sum of the divisors read off a factorisation, and the first sight of a multiplicative function.
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 compute the number of divisors and the sum of the divisors of an integer from its factorisation without listing them, explain why both formulas are readings of the same product, say what it means for an arithmetic function to be multiplicative and why coprimality is required, and classify a number as perfect, abundant or deficient.
Lesson 4 established that $n = p_1^{e_1} \cdots p_k^{e_k}$ in exactly one way, and that $d \mid n$ exactly when $d = p_1^{f_1} \cdots p_k^{f_k}$ with $0 \le f_i \le e_i$ for every $i$.
Read that second sentence as a description of a list. It says the divisors of $n$ are in one-to-one correspondence with the ways of choosing one exponent per prime, within range. Once divisors are a list of choices, counting them and adding them up are both counting problems, and neither needs the divisors written out.
An arithmetic function is a function defined on the positive integers. Two of them appear here: $\tau(n)$ (also written $d(n)$) is the number of divisors of $n$, and $\sigma(n)$ is their sum.
An arithmetic function $f$ is multiplicative when $f(mn) = f(m)f(n)$ for every coprime pair $m, n$ — not for every pair. It is completely multiplicative if the coprimality is not needed, which $\tau$ and $\sigma$ are not.
A number is perfect when $\sigma(n) = 2n$, abundant when $\sigma(n) > 2n$ and deficient when $\sigma(n) < 2n$. Every prime is deficient, and so is every prime power.
Counting. A divisor of $n = \prod p_i^{e_i}$ picks an exponent $f_i \in \{0, 1, \ldots, e_i\}$ for each prime, independently. That is $e_i + 1$ choices for the $i$-th prime, so $$\tau(n) = \prod_{i}(e_i + 1).$$
Summing. The same correspondence, multiplied out: expanding $$\prod_i \left(1 + p_i + p_i^2 + \cdots + p_i^{e_i}\right)$$ produces each divisor exactly once, so that product is $\sigma(n)$. Summing each geometric series gives $$\sigma(n) = \prod_i \frac{p_i^{e_i + 1} - 1}{p_i - 1}.$$
Multiplicativity. Both formulas are products with one factor per prime, so if $\gcd(m, n) = 1$ — meaning no prime appears in both — then $\tau(mn) = \tau(m)\tau(n)$ and $\sigma(mn) = \sigma(m)\sigma(n)$. Coprimality is essential: $\tau(2) = 2$ and $\tau(4) = 3$, not $4$.
This is the first appearance of a pattern that runs through the rest of the course. A multiplicative function is determined by its values on prime powers, so a question about a general $n$ splits into independent questions about each $p^{e}$. Euler's totient in unit 3 is the next one, and it behaves the same way for the same reason.
A consequence worth having. $\tau(n)$ is odd exactly when $n$ is a perfect square, since every exponent must then be even. The divisors otherwise pair up as $d$ with $n/d$, and only a square has a divisor paired with itself.
Another way: steps
Another way: example
$n = 360 = 2^3 \cdot 3^2 \cdot 5$. $\tau(360) = 4 \cdot 3 \cdot 2 = 24$. $\sigma(360) = (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 \cdot 13 \cdot 6 = 1170$. Since $1170 > 720$, $360$ is abundant — comfortably, which is typical of numbers with several small prime factors.
The two formulas look different — one multiplies small integers, the other sums geometric series — and they are the same argument written twice.
Take $n = 12 = 2^2 \cdot 3$ and expand the product $$(1 + 2 + 4)(1 + 3)$$ without collecting terms. You get $1 \cdot 1 + 1 \cdot 3 + 2 \cdot 1 + 2 \cdot 3 + 4 \cdot 1 + 4 \cdot 3$, which is $1 + 3 + 2 + 6 + 4 + 12$: every divisor of $12$, exactly once. Counting the terms gives $\tau(12) = 3 \cdot 2 = 6$; adding them gives $\sigma(12) = 28$.
So the product form is the real object and both functions are readings of it. That is worth noticing because the same product form answers other questions with no new work. The sum of the squares of the divisors is $\prod(1 + p^2 + \cdots + p^{2e})$. The number of divisors that are perfect squares is $\prod(\lfloor e_i/2 \rfloor + 1)$. The product of all the divisors is $n^{\tau(n)/2}$, because the divisors pair off into $\tau(n)/2$ pairs each multiplying to $n$.
It also explains why abundance clusters where it does. $\sigma(n)/n = \prod (1 + 1/p + \cdots + 1/p^{e})$, which is bounded above by $\prod \frac{p}{p-1}$ over the primes dividing $n$. For that to exceed $2$, the small primes have to be involved: $2/1 \cdot 3/2 = 3$ is already enough room, while a product of large primes contributes factors barely above $1$. Every abundant number below $1000$ is even, and the smallest odd one is $945$.
Multiplying without coprimality. $\tau(mn) = \tau(m)\tau(n)$ needs $\gcd(m, n) = 1$. $\tau(2 \cdot 4) = \tau(8) = 4$, while $\tau(2)\tau(4) = 6$. The same trap catches $\sigma$, and it will catch Euler's totient in unit 3.
Forgetting $1$ and $n$. Both are divisors. $\tau(p) = 2$ for a prime, not $0$; $\sigma(p) = p + 1$. The word proper is what excludes $n$, and it is easy to read past.
Using $e_i$ instead of $e_i + 1$. The exponent $0$ is a genuine choice — it is what produces the divisor $1$ — so the number of choices is one more than the exponent.
Assuming the count grows with the number. It does not, even roughly. $\tau$ is $2$ at every prime, however large, and jumps to $16$ at $210$. A number's divisor count is a fact about the shape of its factorisation.
A fifth, subtler one: reading $\sigma(n) = 2n$ as a formula for something. It is a condition, satisfied by a handful of known numbers, and deciding whether any odd number satisfies it is an open problem. A definition is not a construction.
$n = 84 = 2^2 \cdot 3 \cdot 7$. Exponents $2, 1, 1$, so $\tau(84) = 3 \cdot 2 \cdot 2 = 12$.
One more than each exponent.
$\sigma(84) = (1 + 2 + 4)(1 + 3)(1 + 7) = 7 \cdot 4 \cdot 8 = 224$.
One geometric series per prime.
$2n = 168$ and $224 > 168$, so $84$ is abundant; the proper divisors add to $224 - 84 = 140$.
Comparing with $2n$ is the whole classification.
Which numbers have exactly three divisors? $\tau(n) = \prod(e_i + 1) = 3$, and $3$ is prime, so the product has one factor.
A constraint on the factorisation, read off the formula.
So $n$ has a single prime factor and $e_1 + 1 = 3$, giving $n = p^2$.
One prime, exponent two.
The numbers with exactly three divisors are the squares of primes: $4, 9, 25, 49, \ldots$, and their divisors are $1$, $p$ and $p^2$.
The formula answers existence questions as readily as computational ones.
Pair each divisor $d$ with $n/d$, which is also a divisor; each pair multiplies to $n$.
The pairing is the whole idea.
There are $\tau(n)$ divisors, so $\tau(n)/2$ pairs — and when $n$ is a square the middle divisor $\sqrt{n}$ pairs with itself, which is why the exponent can be a half-integer and the formula still holds.
The square case is the one to check rather than to skip.
Multiplying the pairs gives $n^{\tau(n)/2}$.
Match each number to how many positive divisors it has.
| $12$ | $3$ | $8$ | |
|---|---|---|---|
| $96$ | |||
| $25$ | |||
| $30$ |
How many positive divisors does $24$ have?
Answer:
For each number, give how many divisors it has and what they add up to.
| Number of divisors | Sum of divisors | |
|---|---|---|
| $18$ | ||
| $6$ | ||
| $36$ |
For $108 = 2^{2} \cdot 3^{3}$, give the number of divisors and their sum.
number of divisors a, sum of divisors c
Put these three numbers in increasing order of how many divisors they have.
Number the steps in order (write the number in the box):
What do all the positive divisors of $6$ except $6$ itself add up to?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Match each number to how many positive divisors it has.
| $4$ | $6$ | $12$ | |
|---|---|---|---|
| $27$ | |||
| $18$ | |||
| $60$ |
You can compute how many divisors a number has and what they add up to, straight from its factorisation. Say in your own words why a large number can have far fewer divisors than a small one. Next: the other way of splitting the integers, into classes that share a remainder.
9. Your turn: show that the product of all the positive divisors of $n$ is $n^{\tau(n)/2}$, step 3