Counting divisors

Revision as of 23:25, 19 June 2006 by MCrawford (talk | contribs) (rewrote first paragraph and reorganized the rest)

The general task of counting divisors of any integer requires us to organize the divisors of an integer. The prime factorization of the integer gives us a way to describe, and therefore organize, these divisors.


Example: 72

Consider the task of counting the divisors of 72.
$\displaystyle72=2^{3} \cdot 3^{2}.$

Since each divisor of 72 can have a power of 2, and since this power can be 0, 1, 2, or 3, we have 4 possibilities. Likewise, since each divisor can have a power of 3, and since this power can be 0, 1, or 2, we have 3 possibilities. By an elementary counting principle, we have 3*4=12 divisors.


Formula

Generally, If we have a number's prime factorization, the number of divisors is equal to the product of each of the exponents plus one, i.e. $(e_1+1)(e_2+1)\ldots(e_n+1)$ where each of the $e_i$ are the exponents of the nth unique exponentiation base.

See Also