Counting divisors, and perfect numbers
Tonight's idea
Factor first: \(72 = 2^3 \cdot 3^2\). A divisor of 72 uses the same primes with exponents no bigger, so it looks like \(2^a \cdot 3^b\) with \(a\) from 0 to 3 and \(b\) from 0 to 2. Four choices for \(a\), three for \(b\), each pair giving a different divisor: \(4 \times 3 = 12\) divisors, shown below as a grid.
A third prime adds a third direction. \(360 = 2^3 \cdot 3^2 \cdot 5\), so the exponent of 5 is 0 or 1 and there are \(4 \times 3 \times 2 = 24\) divisors. Write \(d(n)\) for the number of divisors of \(n\), counting 1 and \(n\).
If \(n = p^a q^b r^c \cdots\), then \(d(n) = (a+1)(b+1)(c+1)\cdots\). Each exponent can be anything from 0 up to its maximum.
Now add the divisors instead. The divisors of 6 below 6 are 1, 2, 3, and \(1 + 2 + 3 = 6\). A number equal to the sum of its smaller divisors is perfect. Next come 28, 496 and 8128, all even. Euclid gave a recipe for even ones; nobody has ever found an odd one, and whether one exists is still open: see Problems nobody has solved.
Watch one: the smallest number with exactly 12 divisors
Work backwards from the formula. We need exponents whose "plus ones" multiply to 12. The ways to write 12 as a product of numbers bigger than 1 are \(12\), \(6 \times 2\), \(4 \times 3\) and \(3 \times 2 \times 2\). Subtract 1 from each factor to get the exponents, and put the biggest exponents on the smallest primes:
\[2^{11} = 2048, \qquad 2^5 \cdot 3 = 96, \qquad 2^3 \cdot 3^2 = 72, \qquad 2^2 \cdot 3 \cdot 5 = 60.\]
The smallest is 60. Check: \(d(60) = 3 \times 2 \times 2 = 12\).
To check whether a number like 31 or 127 is prime, use the sieve at mathdetours.com/demos/sieve.html.
Your turn
- Find \(d(12)\), \(d(100)\) and \(d(1000)\) from the prime factorisations. Then list the divisors of 12 to confirm the first one.
- Find \(d(16)\), \(d(36)\) and \(d(50)\). Two of the three are odd. Use the formula to explain exactly which numbers have an odd number of divisors.
- \(496 = 2^4 \cdot 31\). How many divisors does it have? List them all, then add every divisor except 496 itself and confirm that 496 is perfect.
- Find the smallest number with exactly 16 divisors. (There are five ways to write 16 as a product of factors bigger than 1. Try them all.)
Stretch: Euclid's recipe
Let \(q = 2^p - 1\) be prime and \(N = 2^{p-1} q\). The divisors of \(N\) are \(1, 2, \ldots, 2^{p-1}\) and those same powers times \(q\). Add each row and show all the divisors total exactly \(2N\). Then take \(p = 13\) (8191 is prime) and write down the fifth perfect number.
Answers
- \(12 = 2^2 \cdot 3\), so \(d(12) = 3 \times 2 = 6\): the divisors are 1, 2, 3, 4, 6, 12. \(100 = 2^2 \cdot 5^2\), so \(d(100) = 3 \times 3 = 9\). \(1000 = 2^3 \cdot 5^3\), so \(d(1000) = 4 \times 4 = 16\).
- \(d(16) = 5\), \(d(36) = 3 \times 3 = 9\), \(d(50) = 2 \times 3 = 6\). The product \((a+1)(b+1)\cdots\) is odd only when every factor is odd, which means every exponent is even. A number whose exponents are all even is a perfect square. So the numbers with an odd number of divisors are exactly the squares. (Divisors pair up as \(k\) and \(n/k\); only a square has a divisor paired with itself.)
- \(d(496) = 5 \times 2 = 10\). Divisors: 1, 2, 4, 8, 16 and 31, 62, 124, 248, 496. The first row adds to 31. The second row, without 496, adds to \(31 \times 15 = 465\). Total \(31 + 465 = 496\).
- \(16 = 16 = 8 \times 2 = 4 \times 4 = 4 \times 2 \times 2 = 2 \times 2 \times 2 \times 2\), giving \(2^{15} = 32768\), \(2^7 \cdot 3 = 384\), \(2^3 \cdot 3^3 = 216\), \(2^3 \cdot 3 \cdot 5 = 120\) and \(2 \cdot 3 \cdot 5 \cdot 7 = 210\). The smallest is 120.
Stretch. The first row \(1 + 2 + \cdots + 2^{p-1}\) adds to \(2^p - 1 = q\). The second row is \(q\) times the first, so it adds to \(q^2\). Total \(q + q^2 = q(q + 1) = q \cdot 2^p = 2N\). Every divisor counted, including \(N\), gives \(2N\), so the divisors below \(N\) add to exactly \(N\): perfect. With \(p = 13\): \(N = 2^{12} \times 8191 = 33{,}550{,}336\). Euler later proved every even perfect number has Euclid's form, so finding perfect numbers means finding primes of the form \(2^p - 1\). Only about fifty are known.