D(n) is the number of divisors of a positive integer n. If the prime factorization of n is
n = (p1e1)(p2e2)...(pk^ek)
then how can you prove that the number of divisors D(n) is
D(n) = (e1 + 1)(e2 + 1) ... (ek + 1)?
For example, 360 = (23)(32)(5^1) and has (3 + 1)(2 + 1)(1 + 1) = 24 distinct divisors.
The divisors of 360 are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, and 360, with 24 total.
In English: If you know the number of divisors of an integer, then why is this number also the same as the product of each power plus 1 of the prime factorization powers of the integer?
It's a nice theorem and the proof is interesting.
Math Challenge: Number Theory & Combinatorics Proof
2 Comments