Suppose $n$ is a composite natural number. Then $n$ has unique prime factorization. To count the number of proper divisors, simply take the product of the exponents +1 in the prime factorization.
$$n = \prod_{i = 1}^{n} p_i^{a_i}$$
$$\mbox{proper divisors} = \prod_{i = 1}^{n}(a_i+1)$$
Is 1 counted multiple times by doing this?
For instance, I can choose from $a_0+1$ factors contributed from $p_0$, namely
$ 1, p_0, p_0^2, \dots , p_0^{a_0} $
Don't I count 1 multiple times?
Answer
You don't count 1 multiple times:
The divisor 1 is only obtained if you choose the exponent $0$ for every prime factor at the same time and the only way of doing that is by choosing every exponent to be $0$; there is only one way of doing it. Hence you do not double count $1$, nor any other divisor.
No comments:
Post a Comment