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 n=p1a1p2a2⋯prarn = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}. Then

τ(n)=(a1+1)(a2+1)⋯(ar+1)\tau(n) = (a_1 + 1)(a_2 + 1)\cdots(a_r + 1) σ(n)=(1+p1+⋯+p1a1)⋯(1+pr+⋯+prar)\sigma(n) = \left(1 + p_1 + \cdots + p_1^{a_1}\right)\cdots\left(1 + p_r + \cdots + p_r^{a_r}\right)

Each bracket in σ\sigma is a geometric sum, pa+1−1p−1\tfrac{p^{a+1} - 1}{p - 1}.

A number is perfect when it equals the sum of its divisors other than itself, that is σ(n)=2n\sigma(n) = 2n.

Why the exponents add one

Every divisor of nn has the form p1b1⋯prbrp_1^{b_1} \cdots p_r^{b_r} with 0≤bi≤ai0 \le b_i \le a_i, and different choices give different divisors, by unique prime factorization. There are ai+1a_i + 1 choices for each exponent, because 00 counts too, so the counting principle gives the product. Expanding the product for σ\sigma produces each such divisor exactly once, which is why it adds them all.

Worked examples

Common mistakes

Practice problems

  1. Find τ(36)\tau(36).

    Answer

    99

    Full solution

    36=22⋅3236 = 2^2 \cdot 3^2, so 3⋅33 \cdot 3.

  2. Find σ(36)\sigma(36).

    Answer

    9191

    Full solution

    (1+2+4)(1+3+9)=7⋅13(1 + 2 + 4)(1 + 3 + 9) = 7 \cdot 13.

  3. Find τ(1000)\tau(1000).

    Answer

    1616

    Full solution

    1000=23⋅531000 = 2^3 \cdot 5^3, so 4⋅44 \cdot 4.

  4. Find σ(12)\sigma(12).

    Answer

    2828

    Full solution

    12=22⋅312 = 2^2 \cdot 3, so (1+2+4)(1+3)=7⋅4(1 + 2 + 4)(1 + 3) = 7 \cdot 4.

  5. Find τ(81)\tau(81).

    Answer

    55

    Full solution

    81=3481 = 3^4: the divisors are 1,3,9,27,811, 3, 9, 27, 81.

  6. Find the smallest number with exactly 66 divisors.

    Answer

    1212

    Full solution

    6=66 = 6 or 2⋅32 \cdot 3: compare 25=322^5 = 32 with 22⋅3=122^2 \cdot 3 = 12.

  7. Find the next perfect number after 2828.

    Answer

    496496

    Full solution

    496=24⋅31496 = 2^4 \cdot 31, and σ(496)=31⋅32=992=2⋅496\sigma(496) = 31 \cdot 32 = 992 = 2 \cdot 496.

  8. A student computes τ(540)\tau(540) as 2⋅3⋅1=62 \cdot 3 \cdot 1 = 6 from 540=22⋅33⋅5540 = 2^2 \cdot 3^3 \cdot 5. Find τ(540)\tau(540).

    Answer

    2424

    Full solution

    Add one to each exponent: 3⋅4⋅23 \cdot 4 \cdot 2.

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.

What to learn next