How many positive integers $n \leq 20000$ have the properties that $2 n$ has 64 positive divisors including 1 and $2 n$, and $5 n$ has 60 positive divisors including 1 and $5 n$ ?
(A) 4
(B) 5
(C) 3
(D) 2
(E) 6
We will use the result that if a positive integer $N$ has prime factorization $N=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$ for some distinct prime numbers $p_{1}, p_{2}, \ldots, p_{k}$ and positive integers $a_{1}, a_{2}, \ldots, a_{k}$, then $N$ has exactly $\left(a_{1}+1\right)\left(a_{2}+1\right) \cdots\left(a_{k}+1\right)$ positive divisors.

This result is based on the following facts:

F1. Every positive integer greater than 1 can be written as a product of prime numbers in a unique way. (If the positive integer is itself prime, this product consists of only the prime number.) This fact is called the "Fundamental Theorem of Arithmetic". This fact is often seen implicitly in finding a "factor tree" for a given integer. For example, 1500 is equal to $2^{2} \times 3^{1} \times 5^{3}$ and there is no other way of writing 1500 as a product of prime numbers. Note that rearranging the same prime factors in a different order does not count as a different factorization.

F2. If $n$ is a positive integer and $d$ is a positive integer that is a divisor of $n$, then the only possible prime factors of $d$ are the prime factors of $n$. For example, if $d$ is a positive divisor of $n=1500$, then the only possible prime factors of $d$ are 2,3 and 5 . This means, for example, that $d$ cannot be divisible by 7 or by 11 or by any other prime number not equal to 2,3 or 5 . $d$ might or might not be divisible by each of 2,3 or 5 .

F3. If $n$ is a positive integer, $d$ is a positive integer that is a divisor of $n$, and $p$ is a prime factor of both $n$ and $d$, then $p$ cannot divide $d$ "more times" than it divides $n$. For example, if $d$ is a positive divisor of $n=1500=2^{2} \times 3^{1} \times 5^{3}$ that is divisible by 5 , then $d$ can be divisible by 5 or by $5^{2}$ or by $5^{3}$ but cannot be divisible by $5^{4}$ or by $5^{5}$ or by any larger power of 5 .

From these facts, the positive divisors of $N=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$ are the integers of the form

$$
d=p_{1}^{b_{1}} p_{2}^{b_{2}} \cdots p_{k}^{b_{k}}
$$

where $b_{1}, b_{2}, \ldots, b_{k}$ are non-negative integers with $0 \leq b_{1} \leq a_{1}, 0 \leq b_{2} \leq a_{2}$, and so on.

This means that there are $a_{1}+1$ possible values for $b_{1}$, namely $0,1,2, \ldots, a_{1}$.

Similarly, there are $a_{2}+1$ possible values for $b_{2}, a_{3}+1$ possible values for $b_{3}$, and so on.

Since every combination of these possible values gives a different divisor $d$, then there are $\left(a_{1}+1\right)\left(a_{2}+1\right) \cdots\left(a_{k}+1\right)$ positive divisors.

Suppose that $n$ has prime factorization $2^{r} 5^{s} p_{3}^{a_{3}} p_{4}^{a_{4}} \cdots p_{k}^{a_{k}}$ for some distinct prime numbers $p_{3}, p_{4}, \ldots, p_{k}$ none of which equal 2 or 5 , for some positive integers $a_{3}, a_{4}, \ldots, a_{k}$, and some non-negative integers $r$ and $s$.

We have written $n$ this way to allow us to pay special attention to the possible prime factors of 2 and 5 .

This means that

$$
\begin{aligned}
& 2 n=2^{r+1} 5^{s} p_{3}^{a_{3}} p_{4}^{a_{4}} \cdots p_{k}^{a_{k}} \\
& 5 n=2^{r} 5^{s+1} p_{3}^{a_{3}} p_{4}^{a_{4}} \cdots p_{k}^{a_{k}}
\end{aligned}
$$

Since $2 n$ has 64 positive divisors and $5 n$ has 60 positive divisors, then

$$
\begin{aligned}
& (r+2)(s+1)\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=64 \\
& (r+1)(s+2)\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=60
\end{aligned}
$$

Since every factor in the two expressions on the left is a positive integer, then

$$
\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)
$$

is a positive common divisor of 64 and of 60 .

The positive divisors of 64 are 1, 2, 4, 8, 16, 32, 64 .

Of these, only 1, 2, 4 are divisors of 60 .

Therefore, $\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)$ equals 1 , 2 or 4 .

Since each of $a_{3}, a_{4}, \ldots, a_{k}$ is a positive integer, then each of $a_{3}+1, a_{4}+1, \ldots, a_{k}+1$ is at least 2.

Case 1: $\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=4$

The only ways in which 4 can be written as a product of positive integers each at least 2 are $2 \times 2$ and 4 (a product of one integer is itself).

Thus, either $k=4$ with $a_{3}+1=a_{4}+1=2$ (giving $a_{3}=a_{4}=1$ ), or $k=3$ with $a_{3}+1=4$ (giving $a_{3}=3$ ).

Since

$$
\begin{aligned}
& (r+2)(s+1)\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=64 \\
& (r+1)(s+2)\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=60
\end{aligned}
$$

then, after simplification, we have

$$
\begin{aligned}
& (r+2)(s+1)=16 \\
& (r+1)(s+2)=15
\end{aligned}
$$

Expanding the left sides of the two equations, we obtain

$$
\begin{aligned}
& r s+r+2 s+2=16 \\
& r s+2 r+s+2=15
\end{aligned}
$$

Subtracting the second of these equations from the first, we obtain $-r+s=1$ and so $s=r+1$. Substituting into the equation $(r+2)(s+1)=16$, we obtain $(r+2)(r+2)=16$. Since $r>0$, then $(r+2)^{2}=16$ gives $r+2=4$ and so $r=2$, which gives $s=3$.

Therefore, we could have $r=2, s=3$.

Combining with the possible values of $a_{3}$ and $a_{4}$, this means that we could have $n=2^{2} 5^{3} p_{3} p_{4}$ for some primes $p_{3}$ and $p_{4}$ not equal to 2 or 5 , or $n=2^{2} 5^{3} p_{3}^{3}$ for some prime $p_{3}$ not equal to 2 or 5 .

We can verify that $2 n$ and $5 n$ have the correct number of positive divisors in each case.

Case 2: $\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=2$

The only way in which 2 can be written as a product of positive integers each at least 2 is 2 .

Thus, $k=3$ with $a_{3}+1=2$ (giving $a_{3}=1$ ).

Since

$$
\begin{aligned}
& (r+2)(s+1)\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=64 \\
& (r+1)(s+2)\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=60
\end{aligned}
$$

then

$$
\begin{aligned}
& (r+2)(s+1)=32 \\
& (r+1)(s+2)=30
\end{aligned}
$$

We could proceed as in Case 1.

Alternatively, knowing that $r$ and $s$ are non-negative integers, then the possibilities from the first equation are

| $r+2$ | $s+1$ | $r$ | $s$ | $r+1$ | $s+2$ | $(r+2)(s+1)$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 32 | 1 | 30 | 0 | 31 | 2 | 62 |
| 16 | 2 | 14 | 1 | 15 | 3 | 45 |
| 8 | 4 | 6 | 3 | 7 | 5 | 35 |
| 4 | 8 | 2 | 7 | 3 | 9 | 27 |
| 2 | 16 | 0 | 15 | 1 | 17 | 17 |
| 1 | 32 | -1 | 31 | 0 | 33 | 0 |

There are no values of $r$ and $s$ that work in this case.

Case 3: $\left(a_{3}+1\right)\left(a_{4}+1\right) \cdots\left(a_{k}+1\right)=1$

Since each factor on the left side is supposedly at least 2 , what can this mean? This actually means that there are no factors on the left side. In other words, $k=2$ and $n=2^{r} 5^{s}$.

(See if you can follow the argument before Case 1 through to verify that there are no contradictions.)

Here,

$$
\begin{aligned}
& (r+2)(s+1)=64 \\
& (r+1)(s+2)=60
\end{aligned}
$$

Knowing that $r$ and $s$ are non-negative integers, then the possibilities from the first equation are

| $r+2$ | $s+1$ | $r$ | $s$ | $r+1$ | $s+2$ | $(r+2)(s+1)$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 64 | 1 | 62 | 0 | 63 | 2 | 126 |
| 32 | 2 | 30 | 1 | 31 | 3 | 93 |
| 16 | 4 | 14 | 3 | 15 | 5 | 45 |
| 8 | 8 | 6 | 7 | 7 | 9 | 63 |
| 4 | 16 | 2 | 13 | 3 | 15 | 51 |
| 2 | 32 | 0 | 31 | 1 | 33 | 33 |
| 1 | 64 | -1 | 63 | 0 | 65 | 0 |

There are no values of $r$ and $s$ that work in this case.

Therefore, combining the results of the three cases, the positive integer $n$ satisfies the given conditions exactly when

- $n=2^{2} 5^{3} p_{3} p_{4}=500 p_{3} p_{4}$ for some primes $p_{3}$ and $p_{4}$ not equal to 2 or 5 , or
- $n=2^{2} 5^{3} p_{3}^{3}=500 p_{3}^{3}$ for some prime $p_{3}$ not equal to 2 or 5 .

Since $n \leq 20000$, then either

- $500 p_{3} p_{4} \leq 20000$ which gives $p_{3} p_{4} \leq 40$, or
- $500 p_{3}^{3} \leq 20000$ which gives $p_{3}^{3} \leq 40$.

It remains to determine the number of pairs of primes $p_{3}$ and $p_{4}$ that are not equal to 2 or 5 with product less than 40 , and the number of primes $p_{3}$ that are not equal to 2 or 5 whose cube is less than 40 .

In the first case, the possibilities are:

$$
3 \times 7=21 \quad 3 \times 11=33 \quad 3 \times 13=39
$$

The order of $p_{3}$ and $p_{4}$ does not matter as switching the order gives the same value for $n$. We note as well that we cannot have both $p_{3}$ and $p_{4}$ at least 7 and have their product at most 40 . In the second case, the only possibility is $p_{3}^{3}=3^{3}$.

This means that there are 4 possible values of $n$ that satisfy the given conditions.