Discrete Math · Undergraduate
Counting Divisors: τ(n), σ(n) and Perfect Numbers
Quick answer
If n = p₁^a₁ p₂^a₂ ⋯ pᵣ^aᵣ, then every divisor of n picks an exponent from 0 to aᵢ for each prime. So the number of divisors is τ(n) = (a₁ + 1)(a₂ + 1)⋯(aᵣ + 1), and the sum of the divisors is σ(n) = (1 + p₁ + ⋯ + p₁^a₁)⋯(1 + pᵣ + ⋯ + pᵣ^aᵣ). For 72 = 2³ · 3², τ = 4 · 3 = 12 and σ = 15 · 13 = 195. A perfect number equals the sum of its proper divisors, so σ(n) = 2n; 6, 28 and 496 are the first three.
What you'll learn
- Count the divisors of n with τ(n)
- Add the divisors of n with σ(n)
- Find the smallest number with a given number of divisors
- Recognize perfect numbers
Divisors from the factorization
Write . Then
Each bracket in is a geometric sum, .
A number is perfect when it equals the sum of its divisors other than itself, that is .
Why the exponents add one
Every divisor of has the form with , and different choices give different divisors, by unique prime factorization. There are choices for each exponent, because counts too, so the counting principle gives the product. Expanding the product for produces each such divisor exactly once, which is why it adds them all.
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
, so .
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
, so .
-
Find .
Answer
Full solution
, so .
-
Find .
Answer
Full solution
: the divisors are .
-
Find the smallest number with exactly divisors.
Answer
Full solution
or : compare with .
-
Find the next perfect number after .
Answer
Full solution
, and .
-
A student computes as from . Find .
Answer
Full solution
Add one to each exponent: .
Frequently asked questions
How do I count the divisors of a number?
Write n = p₁^a₁ ⋯ pᵣ^aᵣ. The number of divisors is (a₁ + 1)(a₂ + 1)⋯(aᵣ + 1).
How do I add up the divisors?
Multiply, over each prime, the sum 1 + p + p² + ⋯ + p^a. Each sum equals (p^(a+1) − 1)/(p − 1).
What is a perfect number?
A number equal to the sum of its divisors other than itself, such as 6 = 1 + 2 + 3. Equivalently, σ(n) = 2n.
Which numbers have an odd number of divisors?
Exactly the perfect squares, since every exponent must be even for each aᵢ + 1 to be odd.