Method to finding the number of factors

Question

I've seen that the number of factors of $x$ can be found:

1. Prime factorising $x$
2. Taking each power in the factorisation and adding $1$
3. Multiplying these numbers together.

This results in the number of factors of $x$.

What I don't understand is the principle behind this. It doesn't seem very intuitive. Could someone please explain this method?

Furthermore how can we prove or be certain that the factorisation of $x$ is even unique?

Answer 1

Let $n$ be a positive integer. Then we can write $n$ as

$$ n = p_1^{e_1} p_2^{e_2} \cdots p_{n}^{e_n} $$

Now we want to get the number of positive factors of $n$. We can think of this as a combinatorics problem.

When we form a factor of n, we compose it from the prime factors $p_1, p_2, ..., p_n$.

In so doing, we have $e_1 + 1$ choices for the first prime factor, $e_2 + 1$ choices for the second prime factor, $e_3 + 1$ choices for the third prime factor, and so on, until we get $e_n + 1$ choices for $p_n$.

Using the multiplicative rule of counting, we have $(e_1 + 1)(e_2 + 1)\cdots(e_n + 1)$ possible factors.

Let's give an example to help make things clear.

Let $n = 300$. We can write $n$ as

$$ n = 2^2 \cdot 3 \cdot 5^2 $$

We can use the formula $d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_n + 1)$ to get the number of positive divisors of $n$.

$$ d(300) = (2 + 1)(1 + 1)(2 + 1) = 18 $$

Thus there are 18 positive divisors (factors) of 300.

We can list these divisors to be sure:

1, 300
2, 150
3, 100
4, 75
5, 60
6, 50
10, 30
12, 25
15, 20

Above we count 18 divisors.

To summarize, we have given the general formula

$$ d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_n + 1) $$

This formula gives us the number of positive divisors of a positive integer. A factor is a divisor. So we can also say it gives us the number of positive factors of a positive integer.

We have explained how this formula works. It is really a combinatorics problem. We used the multiplicative rule of counting to derive the formula. The principle at work here is the multiplicative principle of counting.

The fundamental theorem of arithmetic tells us that every positive integer greater than 1 has a unique prime factorization. That's how we know the prime factorization of n is unique. Without this theorem, we wouldn't be able to derive the formula for $d(n)$. It is also helpful to point out that the domain of $d(n)$ is all positive integers greater than 1. We can use the divisor function $d(n)$ to get the number of factors for a positive integer greater than 1. The variables $e_1, e_2, ..., e_n$ represent the respective powers of each prime factor of n.

---

Additional explanation:

We have $e_k + 1$ choices for the kth prime factor. Let's look at our example of 300. $300 = 2^2 \cdot 3 \cdot 5^2$. We have 3 choices with respect to the prime factor 2, because we can choose from $\{2^0, 2^1, 2^2\} = \{1, 2, 4\}$. We have 2 choices with respect to 3 because we can choose from $\{1, 3\}$. We have 3 choices with respect to 5 because we can choose from $\{1, 5, 25\}$. So we are choosing one element from the set $\{1, 2, 4\}$, one element from the set $\{1, 3\}$, and one element from the set $\{1, 5, 25\}$. According to the multiplication rule of counting, we have $3 \times 2 \times 3 = 18$ choices.

Answer 2

Lets say x can be expressed as

$ x= p^aq^br^cs^d$, where p,q,r,s are prime numbers.

Now, note that any factor of x must divide x. Or in other words, any factor of x is a combination of different powers of p,q,r,s. For instance take 120 as an example.

$120= 2^3×3^1×5^1 $ Any factor of 120 must be a combination of these prime numbers only, or it will not divide 120. If a number has 7 as a prime factor, it will not divide 120.

Also note that any factor of x will be either smaller than or equal to x.

Hence, we can conclude that any factor of x can be expressed as

$p^a¹ q^a² r^a³ s^a⁴$

Where a¹ can range from 0 to a, a² from 0 to b, a³ from 0 to c and a⁴ from 0 to d.

So we have (a+1),(b+1),(c+1),(d+1) choices for the powers of p,q,r,s.

Giving us number of factors as (a+1)(b+1)(c+1)(d+1).