Number of Factors of an Integer

The number of (positive integer) factors of a positive integer $n$ is denoted by $d(n)$. It is one of the most important arithmetic functions.

There exists a simple formula determining the number of factors of an integer. Or rather, as we usually consider positive factors of positive integers, let's restrain ourselves to positive integers.

To understand the formula, let's consider an example. Suppose we wish to find the number of positive divisors of $84$. To do this, a fast method would be to factorize it and then try to find all possible ways to meld its prime factors into a divisor. Let's carry this out - $84=2^2\cdot 3\cdot 7$. This means the divisors are $1,3,7,21$ and their doubles, $2,6,14,42$ and their quadruples, $4,12,28,84$.

More generally, suppose we have a positive integer $n>1$ with the prime factorization* $$n=p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}.$$ (Here, the $p_i$ represent different primes and the $k_i$ are some positive integer exponents.)

Any divisor of $n$ has the form

$$p_1^{\ell_1}p_2^{\ell_2}\dots p_r^{\ell_r}$$

where $0\le \ell_i\le k_i$ for each $k=1,2,...,r$. Note that some of the $\ell_i$ may be $0$. In fact, every number of this form is a divisor of $n$, and such a representation of a divisor is unique*.

Clearly, we may choose these $\ell_1,\ell_2,...,\ell_r$ independently of each other, and for each $i$, we may choose $\ell_i$ to be any of the numbers $0,1,...,k_i$, hence by the multiplication principle, the number of positive divisors of $n$ is precisely

$$d(n)=(k_1+1)(k_2+1)\dots(k_r+1).$$

Based on this formula, we may say that the divisor function is multiplicative.

By generalizing this method, we may find a formula for the sum of factors of a positive integer.

*These claims may appear to be intuitively obvious, but it in fact follow from the Fundamental Theorem of Arithmetic (proven here), which asserts that every integer larger than $1$ has a unique prime factorization.

An important concept in understanding numbers is determining the number of positive factors of an integer. It is not only important to know the techniques that can accomplish this goal, but also why they work. The simplest method for finding the number of factors is to simply list the factors. The easiest way to accomplish this is by looking at factor pairs. A factor pair is two numbers that multiply together to get the integer in question. Consider 30 for example. The following are the factor pairs of 30: $$1\cdot30=30$$ $$2\cdot15=30$$ $$3\cdot10=30$$ $$5\cdot6=30$$ There are 4 factor pairs for 30 and thus there are 8 total factors. Note that we were done looking for factor pairs once we found $5\cdot6$. This is because any other factor pair will include a number less than 5, but we have already considered all possible factors less than 5, so we are done. Try a couple of these on your own:

This works really well for small numbers and it is very important and useful to identify the factor pairs. However, it has two major flaws. First, it is very easy to leave one of the pairs out. The second and more significant flaw is it doesn't scale well. For example, how many factors does 1,000,000 have. The factor pairs are $$1\cdot1,000,000, 2\cdot500,000, 4\cdot250,000...$$ Wait a second, this is going to take forever and 1,000,000 is a pretty easy number to work with. So is there a better way?

YES! And there is a really nice reason why, but lets first describe the algorithm. It starts with a very common practice of finding the prime factorization of the number in question in exponential form. Looking at a couple of our previous examples, $30 = 2\cdot3\cdot5$ and $72=2^3\cdot3^2$ Once we know the prime factorization in exponential form we then look at the exponents. In the case of 30, all three exponents are 1 (note: any integer without a visible exponent, by default, has an exponent of 1). The next part of the algorithm is to add 1 to each exponent. This gets you three new values, all of which are 2. The final step is to multiply these three values together. So: $$(1+1)(1+1)(1+1)=2\cdot2\cdot2$$. For 72 it would be: $$(3+1)(2+1)=4\cdot3=12$$ Both of these are the same amount that we got when looking at the factor pairs. If you take 1,000,000 you get $$1,000,000=2^6\cdot5^6$$ thus the number of factors is: $$(6+1)\cdot(6+1)=49$$ If we would have continued along the method of listing factor pairs we would have had to find 25 factor pairs to get the right answer. Try a couple on your own:

Before we move on to discuss some special cases including what must be true to get an odd number of factors and how we determine how many of the factors are even or odd or perfect squares, lets discuss why this works. The best thing to do is start with a really simple example such as $6=2\cdot3$. There are 4 factors of 6. They are $1, 2, 3, 6$. They can all be represented by powers of 2 and 3 with exponents 0 and 1. Remember that anything to the $0$ power is equal to $1$. So $2^0=1$ and $3^0=1$. So looking at the factors of 6: $$1=2^0\cdot3^0$$ $$2=2^1\cdot3^0$$ $$3=2^0\cdot3^1$$ $$6=2^1\cdot3^1$$ Lets also look at 30: $$1=2^0\cdot3^0\cdot5^0$$ $$2=2^1\cdot3^0\cdot5^0$$ $$3=2^0\cdot3^1\cdot5^0$$ $$5=2^0\cdot3^0\cdot5^1$$ $$6=2^1\cdot3^1\cdot5^0$$ $$10=2^1\cdot3^0\cdot5^1$$ $$15=2^0\cdot3^1\cdot5^1$$ $$30=2^1\cdot3^1\cdot5^1$$

For simplicity, lets also consider $12=2^2\cdot3$ so there are $(2+1)(1+1)=6$ factors. The factors are: $$1=2^0\cdot3^0$$ $$2=2^1\cdot3^0$$ $$3=2^0\cdot3^1$$ $$4=2^2\cdot3^0$$ $$6=2^1\cdot3^1$$ $$12=2^2\cdot3^1$$ As you can see, each of the 3 powers of 2 are combined with each of the 2 powers of 3 to create the 6 factors. Thus, the key component to the algorithm, adding 1 to each exponent, is used so that the exponent of 0 is considered for each unique prime number in the prime factorization.

Factors of Perfect Squares

The number of factors of a perfect square is a special case because there are always an odd number of factors and the only way to get an odd number of factors is to have a perfect square. There are at least two nice explanations of this fact. Can you think of either one?

1. The perfect square $a$ can be written as $a=x^2$, by definition (think $25=5^2$). Thus $a$ has a certain number of factor pairs, one of which is $x\cdot x$. Each of the other factor pairs represents two factors (thus an even number total) and the $x\cdot x$ represents 1 factor, so an even number plus 1 is an odd number.

2. The prime factorization of a perfect square always results in a factorization where all the exponents are even. Thus if 1 is added to each exponent the resulting values are all odd numbers. The product of odd numbers is always odd. Thus the number of factors of an odd number is odd.

How Many Odd Factors?

Think back to why we add 1 to each of the exponents when finding the number of factors. To find the number of odd factors, we think of it the same way, but remove the only way to get an even number, having 2 as a factor. Lets consider 30 again. The odd factors are 1, 3, 5, and 15. These are found as shown: $$1=3^0\cdot5^0$$ $$3=3^1\cdot5^0$$ $$5=3^0\cdot5^1$$ $$15=3^1\cdot5^1$$ Thus we look at all the prime factors except two and perform the algorithm. So we have $(1+1)(1+1)=4$ odd factors.

Lets look at another example. How many odd factors does 450 have? The prime factorization of 450 is $$450=2\cdot3^2\cdot5^2$$ So the number of odd factors is determined by looking adding one to the exponent of 3 and 5. So 450 has $(2+1)(2+1)=9$ odd factors.

How Many Even Factors?

The number of even factors is somewhat difficult to find if considered from a straight forward approach. Instead, we look at it using the following formula. (Total Factors) = (Odd Factors) + (Even Factors). We know that we can calculate the total number of factors and the number of odd factors, thus we just substitute those numbers in and calculate the number of even factors. Lets consider 30 again. We have already calculated that 30 has 8 total factors and 4 odd factors. Thus the total number of even factors is $8-4=4$. Consider the example of 360. The prime factorization is $360=2^3\cdot3^2\cdot5$. The total number of factors is $(3+1)(2+1)(1+1)=24$. The number of odd factors is found by only considering the powers of 3 and 5 so $(2+1)(1+1)=6$. Thus there are 24 total factors and 6 odd factors so the number of even factors is $24-6=18$.

Prove that for any real number $t>0$, there exists a large constant $C(t)>0$ which satisfies

$$d(n)\le C(t)n^t$$

for all positive integers $n$.

For any positive integer $d$, let $f(d)$ denote the smallest positive integer with exactly $d$ divisors.

Let $k$ be a natural number. Prove that $f(2^k)$ divides $f(2^{k+1})$.

(Source: IMO Shortlist 2011, problem N1)