Factors

A factor of an integer $n$ is an integer which can be multiplied by some integer to produce $n.$ Then what is the easiest way to find the number of factors of an integer? If the integer is small (say less than 100), we could try and find all of the factors directly, and then count them. However, this quickly becomes tedious, as we work with larger numbers like 1001.

An integer $k$ is said to be a factor (or divisor) of an integer $N$, if there exists an integer $n$ such that $N = kn.$

In general, the divisors of a number refer to the positive divisors, unless otherwise noted. Since the negative divisors will be the negative of a positive divisor (and vice versa), we shall just consider positive divisors. We also tend to ignore the possibility for any of these numbers to be 0. Also, since $0 = 0 \times m,$ our definition above gives us that every integer is a divisor of $0$.

A proper factor of a number $N$ is a positive integer that is a factor of $N$ other than $N$ or 1. Do not confuse this with a proper divisor of $N$, which is any positive integer that is a factor of $N$ other than $N$ itself. A prime factor of a number $N$ is a positive integer that is a factor of $N$ and is also prime.

From the definition, factors of a number tend to occur in pairs of the form $\left( k, \frac{N}{k} \right)$. This is true except for cases when $N$ is a perfect square, in which case $k = \frac{N}{k} = \sqrt{N}.$

How many factors does $12$ have?

---

We can write $12$ as $1 \times 12, 2 \times 6, 3 \times 4$. So the factors are $1, 2, 3, 4, 6, 12,$ implying $12$ has $6$ factors. $_\square$

Every positive integer $N > 1$ possesses a unique prime factorization given by $p_1 ^{q_1} p_2^{q_2} \ldots p_n ^ {q_n}$, where $p_1, p_2, \ldots , p_n$ are distinct prime numbers, and $q_1, q_2, \ldots, q_n$ are positive integers.

How many factors does 100 have? What is the prime factorization of 100?

---

Since $100 = 1 \times 100 = 2 \times 50 = 4 \times 25 = 5 \times 20 = 10 \times 10$, the factors of 100 are $1, 2, 4, 5, 10, 20, 25, 50, 100.$ Therefore, $100$ has 9 factors in all. Note that 100 has an odd number of factors, which means that is a perfect square.

The prime factors of 100 are 2 and 5 and the highest powers of these contained in 100 are 4 and 25, respectively. So we can write the following prime factorization $100 = 2^2 \times 5^2. \ _\square$

What is the prime factorization of $210$?

---

We start by making a list of factors:

$$\begin{aligned} 210 & = 1 \times 210 \\ &= 2 \times 105 \\ &= 3 \times 70 \\ & = 5 \times 42 \\ &= 6 \times 35 \\ &= 7 \times 30 \\ & = 10 \times 21 \\ &= 14 \times 15. \end{aligned}$$

Hence the factors are $1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210,$ implying $210$ has $16$ factors. The prime factors are 2, 3, 5, and 7, each of which is the highest power contained in 210, so 210 has the prime factorization $210 = 2^1 \times 3^1 \times 5^1 \times 7^1.$ $_\square$

For small numbers, we see that we can slowly list out all of the factors, and count them directly if we have not made any mistakes. However, when the numbers become larger, it can be difficult to ensure that we have actually found all of the factors. We might miss 1 or 2 if we are not careful.

If $N = p_1 ^{q_1} p_2^{q_2} \ldots p_n ^ {q_n}$, then $N$ has $d(N) = (q_1 +1) (q_2 +1) \cdots (q_n + 1)$ divisors.

A proof of this theorem is provided at the end of this section. Let's check it against our previous examples:

• $12 = 2 ^2 \times 3$ has $( 2+1) ( 1 + 1) = 6$ factors.
• $100 = 2^2 \times 5^2$ has $(2+1)( 2+1) = 9$ factors.
• $210 = 2 \times 3 \times 5 \times 7$ has $(1+1)(1+1)(1+1)(1+1) = 16$ factors.

The theorem is true in these examples.

How many divisors does the number $2000$ have?

---

We have $2000 = 2^4 5^3$. Hence, from the above discussion, it has $(4+1)(3+1)=20$ divisors. $_\square$

Note: We can list them out as 1, 2, 4, 8, 16, 5, 10, 20, 40, 80, 25, 50, 100, 200, 400, 125, 250, 500, 1000, 2000. (Can you see why we listed out the divisors this way, instead of in increasing order?)

How many factors does $84000$ have?

---

It can be very difficult to solve this by listing the factors out. We can solve this by prime factorization. The prime factorization of $84000$ is $2 \times 2 \times 2\times 2 \times 2 \times 3 \times 5 \times 5 \times 5 \times 7=2^5 \times 3^1 \times 5^3 \times 7^1.$

Each factor is of the form $2^a 3^b 5^c 7^d$, where $a \in \{0 , 1, 2, 3, 4, 5\}, b \in \{0, 1\}, c \in \{0, 1, 2, 3\}$ and $d \in \{0, 1\}.$ Hence, $a$ has $6$ choices, $b$ has $2$ choices, $c$ has $4$ choices, and $d$ has $2$ choices.

Using rule of product, we can conclude $84000$ has $6 \times 2 \times 4 \times 2 = 96$ factors. $_\square$

What is the smallest integer $N$ that has exactly 14 divisors?

---

Since $14 = 2 \cdot 7$, an integer has exactly 14 divisors if it has the form $p^{13}$ or $p_1 \cdot p_2 ^6$. The smallest number in the first case and second case are $2^{13} = 8192$ and $3 \cdot 2^6 = 192$, respectively. Hence 192 is the smallest integer that has exactly 14 divisors. $_\square$

Let's prove the theorem at the start of this section.

We will use prime factorization and the rule of product to help us count effectively.

Let the integer $N$ have a prime factorization $p_1 ^{q_1} p_2^{q_2} \ldots p_n ^ {q_n}$, where $p_1, p_2, \ldots , p_n$ are distinct prime numbers, and $q_1, q_2, \ldots, q_n$ are positive integers. Let $d$ be a divisor of $N,$ then any prime factor $p$ that divides $d$ must divide $N$, and hence it must be one of $p_1, p_2, \ldots , p_n$.

Without loss of generality, set $p = p_i$. Let the highest power of $p$ that divides $d$ be $p_i^{r_i}$. Then, $p_i^{r_i}$ divides $d$, which in turn divides $N$, and hence $p_i^{r_i}$ must divide $p_i ^{q_i}$, which means that $r_i \leq q_i$. Thus, by considering all the prime factors of $d$, we get that it must have the form $d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n},$ where $0 \leq r_i \leq q_i$ for all $i$.

Conversely, given a number $d$ that has the form $d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n},$ where $0 \leq r_i \leq q_i$ for all $i,$ it is clear that $d$ is a divisor of $N$. As such, we have a complete classification of all the divisors.

How many divisors does the number $N$ have? From the above classification, we can set up a direct bijection between $d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}$ and sets of $n$ integers $( r_1, r_2, \ldots, r_n )$ that satisfy $0 \leq r_i \leq q_i$. For each $r_i$, there are $q_i - 0 + 1 = q_i + 1$ possibilities. Hence, by the product rule, there are going to be $(q_1 +1) (q_2 +1) \ldots (q_n + 1)$ divisors in all. The number of divisors of an integer $N$ is often denoted as the $\tau (N)$ or $\sigma_0 (N)$, which is the divisor function. $_\square$

Given a number $N$, what is the sum of all of its factors?

Normal Method

We first start with looking at small cases, where we can list out all of the factors of a number and add them up.

Find the sum of the factors of $36$.

---

Since $36 = 2 ^2 \times 3 ^2$, we know it has $(2+1)(2+1) = 9$ factors. Next, find the factors: They are $1, 2, 3, 4, 6, 9, 12, 18, 36$. Now add: $1+2+3+4+6+9+12+18+36,$ which yields the answer as $91. \ _\square$

Find the sum of factors of 50.

---

Since $50 = 2 \times 5^2$, we know it has $(1+1) (2+1) = 6$ factors. Next, find the factors: They are $1, 2, 5, 10, 25, 50$. Now add: $1+2+5+10+25+50,$ which yields the answer as $93. \ _\square$

Once again, for small numbers, we can slowly list out all the factors, and be certain that we got all of them. However, with larger numbers, finding the factors can get tedious.

Number Theoretical Approach

If $N = p_1 ^ { q_1} p_2 ^ { q_ 2 } \ldots { p_n}^ {q_n}$, then the sum of the factors of $N$ is

$$\frac{ p_1 ^ { q_ 1 + 1 } - 1 } { p_1 - 1 } \times \frac{ p_2 ^ { q_ 2+ 1 } - 1 } { p_2 - 1 } \times \cdots \times \frac{ p_n ^ { q_ n + 1 } - 1 } { p_n - 1 }.$$

A proof of this theorem is provided at the end of this section. Let's check it against our previous examples:

• $36 = 2^2 \times 3^2$, and the sum of its factors is $\frac{ 2^3 - 1 } { 2-1} \times \frac{ 3^3 - 1 } { 3 -1 } = \frac{ 7 } { 1} \times \frac { 26 } { 2} = 91$.
• $50 = 2 \times 5 ^ 2$, and the sum of its factors is $\frac{ 2^2 -1 } { 2-1 } \times { 5^3 -1 } { 5-1 } = \frac{ 3}{1} \times \frac{ 124 } { 4} = 93$.

The theorem is true in these examples.

What is the sum of factors of $1000?$

---

We start with the prime factorization, which is equal to $2^3 \times 5^3.$

The sum of all the factors of 1000 is $\frac{ 2^4 - 1 } { 2 - 1 } \times \frac{ 5^ 4 - 1 } { 5-1 } = 2340$.

Let's check this against the normal method. The factors of 1000 are as follows:

$$\begin{array} { rr rr rr rr} 1 = 2^ 0 \times 5 ^ 0 &&2 = 2 ^ 1 \times 5 ^ 0 && 4 = 2 ^ 2 \times 5 ^ 0 && 8 = 2 ^ 3 \times 5 ^ 0 \\ 5 = 2^ 0 \times 5 ^ 1 && 10 = 2 ^ 1 \times 5 ^ 1 && 20 = 2 ^ 2 \times 5 ^ 1 && 40 = 2 ^ 3 \times 5 ^ 1 \\ 25 = 2^ 0 \times 5 ^ 2 && 50 = 2^ 1 \times 5 ^ 2 && 100 = 2 ^ 2 \times 5 ^ 2 && 200 = 2 ^ 3 \times 5 ^ 2 \\ 125 = 2^ 0 \times 5 ^ 3 && 250 = 2 ^ 1 \times 5 ^ 3 && 500 = 2 ^ 2 \times 5 ^ 3 && 1000 = 2 ^ 3 \times 5 ^ 3&. \end{array}$$

The sum of these terms is

$$\left( 2^0 + 2^1 + 2^2 + 2^3 \right) \left( 5^0 + 5^1 + 5^2 + 5^ 3\right) = 15 \times 156 = 2340 .\ _\square$$

Suppose that the prime factorization of a positive number $K$ is

$$K=2^2 \times 3^2 \times a^2.$$

If the sum of all the factors of $K$ is $12103,$ what is $a?$

---

By the above formula, the sum of all the factors of the number $K=2^2 \times 3^2 \times a^2$ is

$$\begin{aligned} \frac{(2^3-1)(3^3-1)(a^3-1)}{(2-1)(3-1)(a-1)} =\frac{7\times 26 \times (a^3-1)}{1 \times 2 \times (a-1)}&=\frac{91(a-1)(a^2+a+1)}{a-1}\\\\ &=91(a^2+a+1). \end{aligned}$$

Equating this with $12103$ gives

$$\begin{aligned} 91(a^2+a+1)&=12103\\ a^2+a+1&=133 \\ (a+12)(a-11)&=0\\ a&=11.\ _\square \qquad (\text{since }a>0) \end{aligned}$$

Let's now prove the theorem.

In the previous proof for the number of divisors, we were able to classify all of the divisors. In particular, if $N = p_1 ^ { q_1} p_2 ^ { q_ 2 } \ldots { p_n}^ {q_n}$, then the divisors of the number have the form

$$p_1 ^ { r_1} p_2 ^ { r_ 2 } \ldots { p_n}^ {r_n}, \text{ where } 0 \leq r_i \leq q_i .$$

The solution to the sum of factors of 1000 hints at how we can do the factoring. For each combination of $(r_2, r_3, \ldots r_n)$, if we find the sum of the terms over all possible values of $r_1$, we will obtain

$$\left( p_1 ^ 0 + p_1 ^1 + p_1 ^2 + \cdots+ p_ 1 ^ {q_1} \right) \times p_2 ^ { q_ 2 }\times \cdots\times { p_n}^ {q_n} .$$

The terms in the brackets are a geometric progression, whose sum is given by $\frac{ p_1 ^ { q_1 + 1 } - 1 } { p_1 - 1 }$. This is where the term in our formula appears from.

We repeat this procedure, where we sum up over all possible values of $r_2$, and then $r_3$, and so on and so forth.

The sum of all of these factors would hence be

$$\frac{ p_1 ^ { q_ 1 + 1 } - 1 } { p_1 - 1 } \times \frac{ p_2 ^ { q_ 2+ 1 } - 1 } { p_2 - 1 } \times \cdots \times \frac{ p_n ^ { q_ n + 1 } - 1 } { p_n - 1 }.\ _\square$$

Given a number $N,$ what is the product of all of its factors?

Normal Method

We first start with looking at small cases, where we can list out all of the factors of a number and multiply them.

What is the product of the factors of 15?

---

We see that the factors of 15 are 1, 3, 5, and 15. Multiplying them gives 225. $_\square$

Find the product of the factors of 12.

---

The factors of 12 are 1, 2, 3, 4, 6 and 12. Prime factorization of each factor gives

$$\begin{aligned} 12&=2^2\times3^1\\ 6&=2^1\times3^1\\ 4&=2^2\times3^0\\ 3&=2^0\times3^1\\ 2&=2^1\times3^0\\ 1&=2^0\times3^0. \end{aligned}$$

Now observe that $2^0, 2^1,$ and $2^2$ each appear twice. $3^0$ and $3^1$ each appear three times. Thus the factors are distributed in a symmetrical manner. Hence multiplying all the factors will give

$$\left(2^0\times2^1\times2^2\right)^2\times\left(3^0\times3^1\right)^3=2^{2\times(0+1+2)}\times3^{3\times(0+1)}=1728.\ _\square$$

Once again, for small numbers, we can slowly list out all the factors. However, with larger numbers, findinig the factors can get tedious, and multiplying them could lead to a lot of errors.

Number Theoretic Approach

Suppose we have an integer $N = p_1^{q_1}p_2^{q_2}\ldots p_n^{q_n}$. It has $d(N)$ factors. Then, the product of its factors is

$$\large N^ { \frac{ d(N)} {2} }.$$

A proof of this theorem is provided at the end of this section. Let's check it against our previous examples:

Find the product of all factors of 7056.

---

We have $7056=2^4\times3^2\times7^2$, which implies that the number of factors $7056$ has is

$$N=(4+1)\times(2+1)\times(2+1)=45.$$

Therefore the product of all its factors is

$$7056^{\frac{45}{2}}=\left(2^4\times3^2\times7^2\right)^{\frac{45}{2}}=2^{90}\times3^{45}\times7^{45}.\ _\square$$

Consider an integer $n$ which has 6 factors. If the product of all its factors is 8000, what is $n?$

---

Using the formula above, we have

$$n^{\frac{6}{2}}=n^3=8000\implies n=20.\ _\square$$

Let's now prove the theorem.

Let us denote $d(n)$ to be the number of positive divisors $n$ has. We want to find a closed form of the product of all positive divisors of $n.$

As mentioned, notice that for any divisor $k$ of $n$, we have $k\times \frac{n}{k} = n,$ so $\frac{n}{k}$ is also a divisor of $n.$

Let's list out all of these.

Taking the product of the pairs of number, the LHS will give us product square. The RHS gives us $n ^ { d(n) }$. Hence, the product of the divisors is $n ^ { d(n) / 2 }$. $_\square$

Show that an integer $N$ has an odd number of divisors if and only if it is a perfect square.

---

Since $\phi(N) = (q_1 +1)(q_2+1) \cdots (q_n+1)$, this product is odd if and only if every term is odd, which happens if and only if every value $q_i$ is even, which happens if and only if $N$ is a perfect square. $_\square$

The prime factorization of a positive number $M$ is $M=a^2 \times b^2,$ and the sum of all the factors of $M$ is $403.$ Then what is $a+b?$

---

By the above formula, the sum of all the factors of the number $M=a^2 \times b^2$ is

$$\begin{aligned} \frac{(a^3-1)(b^3-1)}{(a-1)(b-1)} &=(a^2+a+1)(b^2+b+1)\\ &=403\\ &=13 \times 31. \end{aligned}$$

Without loss of generality, let $a^2+a+1=13,$ then $a^2+a-12=(a+4)(a-3)=0$ implies $a=3.$ Then letting $b^2+b+1=31,$ we have $(b+6)(b-5)=0,$ which implies $b=5.$ Thus, $a+b=8.$ $_\square$

What is the smallest integer $N$ that has exactly 14 divisors?

---

Since $14 = 2 \cdot 7$, an integer has exactly 14 divisors if it has the form $p^{13}$ or $p_1 \cdot p_2 ^6$. The smallest number in the first case and second case are $2^{13} = 8192$ and $3 \cdot 2^6 = 192$, respectively. Hence 192 is the smallest integer that has exactly 14 divisors. $_\square$

1. What is the smallest integer $N$ which has exactly 10 divisors?
2. What is the smallest integer $N$ which has exactly 9 divisors?
3. Which integer less than 100 has the most number of factors?
4. What is the sum of the factors of 1234?

Recap of Properties:

$(1)$ If $b \mid c$ and $c \mid a,$ then $b \mid a:$ that is, divisibility is transitive.

$(2)$ If $b \mid a$ and $b \mid c,$ then $b \mid (a \pm c):$ that is, the set of multiples of an integer is closed under addition and subtraction operations.

By using this property repeatedly, we have the following: if $b \mid a$ and $b \mid c$, then $b \mid (au+cv)$ for any integers $u$ and $v$. In general, if $a_1,a_2,\ldots,a_n$ are multiples of $b$, then

$$b \mid (a_1+a_2+\cdots+a_n).$$

$(3)$ If $b \mid a$, then $a=0$ or $\lvert a \rvert \geq \lvert b \rvert$. Thus, if $b \mid a$ and $a \mid b$, then $\lvert a \rvert = \lvert b \rvert$.

Clearly, for any two integers $a$ and $b$, $a$ is not always divisible by $b$. But we have the following result, which is called the division algorithm. It is the most important result in elementary number theory.

$(4)$ The Division Algorithm

Let $a$ and $b$ be integers, and $b > 0$. Then there is a unique pair of integers $q$ and $r$, such that

$$a=bq+r \hspace{2mm} \text{and} \hspace{2mm} 0 \leq r < b.$$

The integer $q$ is called the (incomplete) quotient when $a$ is divided by $b$, and $r$ is called the remainder. Note that the values of $r$ has $b$ kinds of possibilities: $0,1,\cdots,b-1.$ If $r=0$, then $a$ is divisible by $b$.

It is easy to see that the quotient $q$ in the division algorithm is in fact $\left\lfloor\frac{a}{b}\right\rfloor$ $\big($the greatest integer not exceeding $\frac{a}{b}\big),$ and the heart of the division algorithm is the inequality about the remainder $r$: $0 \leq r < b$. We will go back to this point later on.

The basic method of proving $b \mid a$ is to factorize $a$ into the product of $b$ and another integer. Usually, in some basic problems this kind of factorization can be obtained by taking some special value in algebraic factorization equations. The following two factorization formulae are very useful in proving this kind of problems.

$(5)$ If $n$ is a positive integer, then

$$x^n-y^n=(x-y)\big(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}\big).$$

$(6)$ If $n$ is a positive odd number, then

$$x^n+y^n=(x+y)\big(x^{n-1}-x^{n-2}y+\cdots-xy^{n-2}+y^{n-1}\big).$$

Examples:

Prove that $1\underbrace{0\ldots 0}_{200}1$ is divisible by $1001$.

---

By $(6)$, we have

$$\begin{aligned} 1\underbrace{0\ldots 0}_{200}1 &=10^{201}+1\\ &=\big(10^3\big)^{67}+1\\ &=\big(10^3+1\big)\left[\big(10^3\big)^{66}-\big(10^3\big)^{65}+\cdots -10^3+1\right]\\ &=1001\left[\big(10^3\big)^{66}-\big(10^3\big)^{65}+\cdots -10^3+1\right]. \end{aligned}$$

Therefore, $1001$ divides $1\underbrace{0\ldots 0}_{200}1$. $_\square$

Let $a$ and $b$ be integers such that $a>b\geq 0$. Show that

$$\big(2^{2^b}+1\big){\Large\mid} \big(2^{2^a}-1\big).$$

---

Take $x=2^{2^{b+1}}$ and $y=1$ in $(5)$, and substitute $n$ by $2^{a-b-1}$. Then we have

$$2^{2^a}-1=\big(2^{2^{b+1}}-1\big)\left[\big(2^{2^{b+1}}\big)^{2^{a-b-1}-1}+\cdots+2^{2^{b+1}}+1\right].$$

Thus,

$$\big(2^{2^{b+1}}-1\big) {\Large\mid} \big(2^{2^a}-1\big).$$

Since

$$2^{2^{b+1}}-1=\big(2^{2^b}-1\big)\big(2^{2^b}+1\big),$$

it follows that

$$\big(2^{2^b}+1\big){\Large\mid} \big(2^{2^{b+1}}-1\big).$$

By $(1)$, we have

$$\big(2^{2^b}+1\big){\Large\mid} \big(2^{2^a}-1\big),$$

and we are done. $_\square$

For a positive integer $n$, let $S(n)$ denote the sum of digits of $n$.

Show that $9\mid n$ if and only if $9\mid S(n)$.

---

Write $n=a_k\times 10^k +\cdots + a_1\times 10 + a_0$ $($where $0\leq a_i \leq 9$ and $a_k \neq 0),$ then $S(n)=a_0+a_1+\cdots+a_k$. We have

$$n-S(n)=a_k\big(10^k-1\big)+\cdots+a_1(10-1). \qquad (1)$$

For $1 \leq i \leq k$, from $(5)$ we get $9 \mid (10^i-1)$. So each of the $k$ terms on the RHS of $(1)$ is a multiple of $9,$ so $(2)$ implies that their sum is also a multiple of $9$, that is, $9 {\large\mid} \big(n-S(n)\big)$. Hence, the result can be obtained easily. $_\square$

Let $k \geq 1$ be an odd integer. Prove that for any positive integer $n$, $1^k+2^k+\cdots+n^k$ is not divisible by $n+2$.

---

When $n=1,$ the statement is obviously true. For $n \geq 2$, denote the sum by $A$. Then

$$2A=2+\big(2^k+n^k\big)+\big(3^k+(n-1)^k\big)+\cdots+\big(n^k+2^k\big).$$

Since $k$ is a positive odd integer, from $(6)$ we know that for every $i \geq 2$, $i^k+(n+2-i)^k$ is divisible by

$$i+(n+2-i)=n+2.$$

Thus, $2A$ has remainder $2$ when divided by $n+2$, which implies that $A$ is not divisible by $n+2$ $($note that $n+2>2).$ $_\square$