Try the code and the simulations beside the lesson.
What you will be able to do
count the divisors of a number, and the divisors with a given property, from its factorisation;
add the divisors with the formula for σ(n);
use the pairing of divisors, and prove Euclid's rule for even perfect numbers.
How many ways to make a rectangle?
You have 504 unit squares and want to arrange them in a rectangle. Each rectangle needs a width that divides 504. How many widths are there? Listing them takes a while. A formula takes a second.
The number of divisors
Write 504=23⋅32⋅7. By the fundamental theorem, every divisor is 2i⋅3j⋅7k with
0≤i≤3,0≤j≤2,0≤k≤1.
Each choice gives a different divisor. There are 4×3×2=24 choices.
 In general, for n=p1a1p2a2⋯pkak,
τ(n)=(a1+1)(a2+1)⋯(ak+1).
The Greek letter τ (tau) is the usual name. Many books write d(n) instead, and some write σ0(n).
Divisors with a property. Restrict the exponents.
Even divisors of 504:i≥1, so 3×3×2=18.
Odd divisors:i=0, so 1×3×2=6.
Square divisors: all exponents even: i∈{0,2}, j∈{0,2}, k=0, so 2×2×1=4.
The sum of the divisors
Expand this product:
(1+2+4+8)(1+3+9)(1+7).
Each term of the expansion picks one power of each prime, so each term is one divisor of 504, and each divisor appears once. So the product is the sum of all divisors: 15×13×8=1560. With the sum of a geometric series,
Multiplicative. If gcd(m,n)=1, then τ(mn)=τ(m)τ(n) and σ(mn)=σ(m)σ(n). The primes of m and of n do not mix. For numbers that share a prime it fails: τ(2×2)=3, but τ(2)τ(2)=4.
Divisors come in pairs
If d∣n, then dn∣n as well. Pair each divisor with its partner. For n=36: 1 with 36, 2 with 18, 3 with 12, 4 with 9, and 6 with itself.
A divisor is its own partner only when d2=n. So τ(n) is odd exactly when n is a perfect square. You can also see it from the formula: all the ai+1 are odd exactly when all the ai are even.
Multiplying each pair gives n. So the product of all the divisors of n is nτ(n)/2.
In each pair one divisor is at most n. So τ(n)≤2n.
Perfect numbers
The Greeks called a number perfect when it equals the sum of its divisors other than itself. For example 6=1+2+3 and 28=1+2+4+7+14. In symbols, σ(n)=2n. The next ones are 496 and 8128.
Euclid's rule. If 2p−1 is prime, then n=2p−1(2p−1) is perfect.
Proof. Put q=2p−1, a prime, so q is odd and coprime to 2p−1. Then
σ(n)=σ(2p−1)σ(q)=(2p−1)(q+1)=q⋅2p=2n.
Proof complete. About two thousand years later Euler proved the converse: every even perfect number has this form. Nobody knows whether an odd perfect number exists. It is one of the oldest open questions in mathematics.
By the problem on Mersenne numbers in course 1, 2p−1 can be prime only when p is prime. The primes 2p−1 are the Mersenne primes, and each gives one even perfect number.
Practise with new numbers
Try it in Python
The program lists the divisors of 504 in pairs, compares the count and the sum with the formulas, and searches for perfect numbers below 10000.
Common mistakes
Multiplying the exponents.τ(23⋅32)=4×3=12, not 3×2=6. Each exponent can also be 0.
Forgetting 1 and n. Both are divisors, and the formula counts them.
Using the multiplicative rule for numbers that share a prime.
Thinking every 2p−1(2p−1) is perfect. It needs 2p−1 to be prime. For p=11 it is not.
Remember these
τ(n)=∏(ai+1) and σ(n)=∏pi−1piai+1−1.
To count divisors with a property, restrict the exponents.
τ(n) is odd exactly when n is a square.
The product of the divisors of n is nτ(n)/2.
2p−1(2p−1) is perfect when 2p−1 is prime, and every even perfect number has this form.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
How many divisors does 25⋅33⋅112 have?
Find the sum of the divisors of 392.
How many divisors of 24⋅36 are perfect cubes?
Which whole numbers have exactly 3 divisors?
Check that 28=22(23−1) is perfect with the formula for σ.
References
David M. Burton, Elementary Number Theory, Chapter 6, section 6.1 on the number and the sum of the divisors, and Chapter 11 on perfect numbers.
Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, Chapter 4 on arithmetic functions.
Enroll free in Common Factors, the Euclidean Algorithm and Divisors
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.