Chapter
Theory
Divisor counting turns a number into a list of prime exponents. If \(n=p_1^{a_1}\cdots p_s^{a_s}\), then each divisor is obtained by independently choosing exponents \(0,1,\ldots,a_i\).
The olympiad strength of the method appears when we do not merely count, but reconstruct the form of a number from its number of divisors or find the smallest number with a prescribed number of divisors.
If the statement says “exactly \(k\) divisors”, immediately factor \(k\) into factors of the form \(a_i+1\). If the smallest number is requested, enumerate possible exponent patterns, not the numbers themselves.
If odd divisors are requested, remove the power of \(2\). If you need to prove oddness of \(\tau(n)\), use divisor pairing around \(\sqrt{n}\).
Examples
The main step is to pass from the number to prime exponents.
Problem. Find the number of positive divisors of \(360\).
\(360=2^3\cdot3^2\cdot5\). A divisor has the form \(2^a3^b5^c\), where \(a=0,1,2,3\), \(b=0,1,2\), \(c=0,1\). Therefore \(\tau(360)=4\cdot3\cdot2=24\).
Comment. Exponent \(0\) means that the prime factor is absent from the divisor.
To count odd divisors, the power of two is irrelevant.
Problem. How many positive odd divisors does \(720\) have?
\(720=2^4\cdot3^2\cdot5\). An odd divisor contains no factor \(2\), so we choose only exponents of \(3\) and \(5\). This gives \((2+1)(1+1)=6\) odd divisors.
Comment. The odd part is \(3^2\cdot5\).
Divisors usually come in pairs; a square gives one unpaired divisor.
Problem. Prove that \(\tau(n)\) is odd if and only if \(n\) is a square.
If \(d\mid n\), then \(\frac{n}{d}\mid n\). Usually divisors pair as \(d\) and \(\frac{n}{d}\). An unpaired divisor can occur only when \(d=\frac{n}{d}\), i.e. \(d^2=n\). Hence the number of divisors is odd exactly for squares.
Comment. This proof does not require the formula for \(\tau(n)\), but explains it well.
Minimisation uses exponent patterns, not brute force over numbers.
Problem. Find the smallest positive integer with exactly \(12\) positive divisors.
We need to write \(12\) as a product of numbers \(a_i+1\). The important possibilities are \(12\), \(6\cdot2\), \(4\cdot3\), \(3\cdot2\cdot2\). They give candidates \(2^{11}\), \(2^5\cdot3=96\), \(2^3\cdot3^2=72\), \(2^2\cdot3\cdot5=60\). The smallest is \(60\). Answer: \(60\).
Comment. Larger exponents go on smaller primes.
Although the module is about \( au\), it is useful to see the neighbouring function \(\sigma\).
Problem. Find the sum of positive divisors of \(72\).
\(72=2^3\cdot3^2\). The sum of divisors is \((1+2+2^2+2^3)(1+3+3^2)=15\cdot13=195\).
Comment. This idea returns later in arithmetic-function modules.
For \(n^2\), all exponents double.
Problem. If \(n=2^3\cdot3^2\cdot5\), find \(\tau(n^2)\).
Then \(n^2=2^6\cdot3^4\cdot5^2\). Hence \(\tau(n^2)=(6+1)(4+1)(2+1)=7\cdot5\cdot3=105\).
Comment. No need to compute the number \(n^2\) itself.
A prescribed number of divisors restricts the form of the number.
Problem. Describe all positive integers \(n\) with exactly \(4\) positive divisors.
We need \((a_1+1)\cdots(a_s+1)=4\). The possibilities are \(4\) or \(2\cdot2\). Therefore \(n=p^3\) for a prime \(p\), or \(n=pq\), where \(p\) and \(q\) are distinct primes.
Comment. This is the first step toward inverse problems for \(\tau(n)\).
Pairing divisors helps find their product.
Problem. Prove that the product of all positive divisors of \(n\) equals \(n^{\tau(n)/2}\).
Each divisor \(d\) corresponds to \(\frac{n}{d}\), and the product of the pair is \(n\). Therefore the product of all divisors is \(n\) multiplied once for each pair. The number of pairs is \(\frac{\tau(n)}{2}\). If \(n\) is a square, the middle divisor \(\sqrt{n}\) is accounted for by the same formula, and the result is still correct.
Comment. For a square, the exponent can be half-integer, but the value is still an integer.
Problems
Find the number of positive divisors of \(84\).
Factor \(84\) into primes.
\(84=2^2\cdot3\cdot7\). Hence \(\tau(84)=(2+1)(1+1)(1+1)=12\).
Find \(\tau(144)\).
\(144=12^2\).
\(144=2^4\cdot3^2\). Thus \(\tau(144)=(4+1)(2+1)=15\).
How many positive divisors does \(2^5\cdot3^3\) have?
Choose the exponent of \(2\) and the exponent of \(3\).
The exponent of \(2\) can be chosen in \(6\) ways, and the exponent of \(3\) in \(4\) ways. Total: \(6\cdot4=24\) divisors.
Prove that \(p^a\), where \(p\) is prime, has exactly \(a+1\) positive divisors.
Which powers of \(p\) can divide \(p^a\)?
Every positive divisor of \(p^a\) has the form \(p^k\), where \(k=0,1,\ldots,a\). There are \(a+1\) choices for \(k\). Hence there are \(a+1\) divisors.
How many positive odd divisors does \(48\) have?
Use \(48=2^4\cdot3\).
An odd divisor contains no factor \(2\), so it can only be \(1\) or \(3\). Answer: \(2\) odd divisors.
Find \(\tau(360)\).
Use \(360=2^3\cdot3^2\cdot5\).
\(\tau(360)=(3+1)(2+1)(1+1)=4\cdot3\cdot2=24\).
Find the number of positive divisors of \(1000\).
\(1000=10^3\).
\(1000=2^3\cdot5^3\). Therefore \(\tau(1000)=(3+1)(3+1)=16\).
How many odd divisors does \(720\) have?
Remove the factor \(2^4\).
\(720=2^4\cdot3^2\cdot5\). The odd part is \(3^2\cdot5\), so the number of odd divisors is \((2+1)(1+1)=6\).
Without listing all divisors, explain why \(\tau(225)\) is odd.
Check whether \(225\) is a square.
\(225=15^2\) is a square. A square has an odd number of positive divisors, because the divisor \(\sqrt{225}=15\) is unpaired. Hence \(\tau(225)\) is odd.
Find the smallest positive integer with exactly \(8\) positive divisors.
Factorisations of \(8\): \(8\), \(4\cdot2\), \(2\cdot2\cdot2\).
Candidates: \(2^7=128\), \(2^3\cdot3=24\), \(2\cdot3\cdot5=30\). The smallest is \(24\). Answer: \(24\).
Find the smallest positive integer with exactly \(10\) positive divisors.
Possibilities: \(10\) or \(5\cdot2\).
Candidates: \(2^9=512\) and \(2^4\cdot3=48\). The smallest number is \(48\).
Find all positive integers less than \(100\) with exactly \(3\) positive divisors.
A number with three divisors has the form \(p^2\).
If \(\tau(n)=3\), then \(n=p^2\) for a prime \(p\). We need \(p^2<100\), so \(p<10\). The primes are \(2,3,5,7\). The numbers are \(4,9,25,49\).
Prove that a positive integer has an odd number of positive divisors if and only if it is a square.
Pair divisors as \(d\) and \(\frac{n}{d}\).
If \(d\mid n\), then \(\frac{n}{d}\mid n\). Divisors come in pairs except when \(d=\frac{n}{d}\), i.e. \(d^2=n\). Thus an unpaired divisor exists exactly when \(n\) is a square. Hence the number of divisors is odd exactly for squares.
Find the smallest positive integer with exactly \(15\) positive divisors.
\(15=15\) or \(15=5\cdot3\).
The exponent patterns are \(14\), or \(4\) and \(2\). Candidates: \(2^{14}\) and \(2^4\cdot3^2=144\). The smallest number is \(144\).
Find the smallest positive integer with exactly \(24\) positive divisors.
Check factorisations of \(24\) into factors \(a_i+1\).
Important candidates are \(2^7\cdot3^2=1152\), \(2^5\cdot3^3=864\), \(2^5\cdot3\cdot5=480\), \(2^3\cdot3^2\cdot5=360\), \(2^2\cdot3\cdot5\cdot7=420\). The smallest is \(360\), and the remaining patterns with larger exponents are larger. Answer: \(360\).
Find \(\tau(360^2)\).
Do not compute \(360^2\); double the exponents.
\(360=2^3\cdot3^2\cdot5\). Then \(360^2=2^6\cdot3^4\cdot5^2\), so \(\tau(360^2)=7\cdot5\cdot3=105\).
Find the product of all positive divisors of \(36\).
Use the formula \(n^{\tau(n)/2}\).
\(36=2^2\cdot3^2\), so \(\tau(36)=9\). The product of divisors is \(36^{9/2}=6\cdot36^4\). This is the exact value.
Describe all positive integers with exactly \(4\) positive divisors.
Write \(4\) as \(4\) and \(2\cdot2\).
If \(\tau(n)=4\), the possible exponent patterns are \(3\), or \(1\) and \(1\). Therefore \(n=p^3\) for a prime \(p\), or \(n=pq\), where \(p,q\) are distinct primes.
Describe all positive integers \(n\) with exactly two positive odd divisors.
Consider the odd part of the number.
Let \(n=2^a m\), where \(m\) is odd. The odd divisors of \(n\) are exactly the divisors of \(m\). We need \(\tau(m)=2\), so \(m\) is an odd prime. Therefore \(n=2^a p\), where \(a\ge0\), and \(p\) is an odd prime.
Find the number of positive divisors of \(10^6\).
\(10^6=2^6\cdot5^6\).
\(10^6=2^6\cdot5^6\), so \(\tau(10^6)=(6+1)(6+1)=49\).
Find the smallest positive integer with exactly \(36\) positive divisors.
Compare the main factorisations of \(36\): \(9\cdot4\), \(6\cdot6\), \(6\cdot3\cdot2\), \(4\cdot3\cdot3\), \(3\cdot3\cdot2\cdot2\).
Candidates are \(2^8\cdot3^3=6912\), \(2^5\cdot3^5=7776\), \(2^5\cdot3^2\cdot5=1440\), \(2^3\cdot3^2\cdot5^2=1800\), \(2^2\cdot3^2\cdot5\cdot7=1260\). The smallest is \(1260\). Other patterns with a larger single exponent are even larger. Answer: \(1260\).
Find the smallest odd positive integer with exactly \(12\) positive divisors.
Use primes \(3,5,7,\ldots\) instead of \(2,3,5,\ldots\).
For \(12\) divisors, the exponent patterns are as before. Odd candidates include \(3^{11}\), \(3^5\cdot5\), \(3^3\cdot5^2\), \(3^2\cdot5\cdot7=315\). The smallest is \(315\). Answer: \(315\).
Find all positive integers \(n\) such that \(\tau(2n)=2\tau(n)\).
Let \(n=2^a m\), where \(m\) is odd.
Let \(n=2^a m\), with \(m\) odd. Then \(\tau(n)=(a+1)\tau(m)\), while \(\tau(2n)=(a+2)\tau(m)\). The condition gives \(a+2=2(a+1)\), hence \(a=0\). Thus \(n\) must be odd. All odd \(n\) work.
Find the smallest positive integer with exactly \(60\) positive divisors.
Put exponents in decreasing order and compare multiplicative decompositions of \(60\).
To minimise the number, it is enough to consider \(2^{a_1}3^{a_2}5^{a_3}\cdots\), where \(a_1\ge a_2\ge a_3\ge\cdots\). We need \((a_1+1)(a_2+1)\cdots=60\). The main candidates are \(2^9\cdot3^2\cdot5=23040\), \(2^5\cdot3^4\cdot5=12960\), \(2^4\cdot3^3\cdot5^2=10800\), \(2^4\cdot3^2\cdot5\cdot7=5040\). Patterns with one or two very large exponents are even larger. The smallest candidate is \(5040\), and \(\tau(5040)=\tau(2^4\cdot3^2\cdot5\cdot7)=5\cdot3\cdot2\cdot2=60\). Answer: \(5040\).
Ladders