Wednesday, 8 May 2013

Double counting the number of proper divisors




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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...