2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your notation is suspect because $n$ is used both as the left hand side and as the limit of the index. Rarely does $n$ have $n$ distinct prime factors, if that is what you want to convey. $\endgroup$ – hardmath Jan 17 '17 at 21:04
  • $\begingroup$ With this product you count all divisors, not only the proper ones. $\endgroup$ – ajotatxe Jan 17 '17 at 21:07
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

In order to count one, the exponent on each prime factor has to be zero. So you are only counting it once.

$\endgroup$
0
$\begingroup$

As an example of how this works, consider the factors of $72 = 2^3\cdot 3^2$.

The factors are:

$$\begin {array}{c} 1 & 2 & 4 & 8 \\ 3 & 6 & 12 & 24 \\ 9 & 18 & 36 & 72 \end{array}$$

As you can see in this $(3{+}1)\times (2{+}1) $ array, $1$ only occurs once as the multiplication process produces another prime power factors otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.