2016 AMC 10A Problem 22

P21-25~6 minPrint

Divisibility & Factors Primes Bound the quantity above/below or estimate to pin it down Set up the equation/formula and compute; no special trick needed

For some positive integer $n$ , the number $110n^3$ has $110$ positive integer divisors, including $1$ and the number $110n^3$ . How many positive integer divisors does the number $81n^4$ have?

Show solution without answering

Key insight

The primes 2, 5 and 11 each add a factor of at least 2 to the divisor count 110 = 2 times 5 times 11, leaving nothing for other primes.

Solution

The divisor-count rule. Write a number as a product of prime powers, add $1$ to each exponent, and multiply. For example $12 = 2^2 \cdot 3^1$ has $(2+1)(1+1) = 6$ divisors: $1, 2, 3, 4, 6, 12$ .

1. What cubing does. Cubing $n$ multiplies every exponent by $3$ . So in $n^3$ every prime has an exponent that is a multiple of $3$ : $0, 3, 6, \ldots$
2. What multiplying by $110 = 2 \cdot 5 \cdot 11$ does. It adds $1$ to the exponents of $2$ , $5$ and $11$ . So in $110n^3$ :
- each of $2$ , $5$ , $11$ has exponent $1, 4, 7, \ldots$ and gives a factor of $2, 5, 8, \ldots$ to the divisor count;
- any other prime in $n$ has exponent $3, 6, \ldots$ and gives a factor of $4, 7, \ldots$
3. Match with $110$ . The divisor count is $110 = 2 \cdot 5 \cdot 11$ , a product of just three primes. The primes $2$ , $5$ , $11$ always give three factors, each at least $2$ , so each of those three factors must be a single prime from $2, 5, 11$ , and nothing is left over. That means:
- $n$ has no primes other than $2$ , $5$ and $11$ ;
- the three factors are $2$ , $5$ and $11$ in some order.
4. Back to exponents. A factor of $2$ means exponent $1$ in $110n^3$ (exponent $0$ in $n$ ). A factor of $5$ means exponent $4$ (exponent $1$ in $n$ ). A factor of $11$ means exponent $10$ (exponent $3$ in $n$ ). So among $2, 5, 11$ , one prime is missing from $n$ , one appears once, and one appears cubed. One example is $n = 2^3 \cdot 5 = 40$ . Check: $110 \cdot 40^3 = 2^{10} \cdot 5^4 \cdot 11$ , with $11 \cdot 5 \cdot 2 = 110$ divisors.
5. Now $81n^4$ . Raising to the 4th power multiplies the exponents by $4$ : one prime to the $4$ th, another to the $12$ th. And $81 = 3^4$ brings in the prime $3$ , which is not in $n$ . So
$81n^4 = 3^4 \cdot p^4 \cdot q^{12}$
for two different primes $p, q$ from $2, 5, 11$ . With $n = 40$ this is $3^4 \cdot 5^4 \cdot 2^{12}$ .
6. The divisor count is $(4 + 1)(4 + 1)(12 + 1) = 5 \cdot 5 \cdot 13 = 325$ , whichever primes $p$ and $q$ are.

The answer is $\boxed{\textbf{(D)}\ 325}$ .

Why this works

The number of divisors depends only on the exponents in the prime factorization. Cubing makes every exponent a multiple of $3$ , and multiplying by $110$ bumps three of them by one, so the primes of $110$ behave differently from all other primes. Since $110$ has only three prime factors, there is no room for anything else. We never had to find $n$ exactly: every possible $n$ gives the same final count.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Write $n = 2^a 5^b 11^c \cdot k$ where $k$ has no factor of $2$ , $5$ or $11$ , and let the primes of $k$ have exponents $e_1, e_2, \dots$ in $n$ . Then
$110 n^3 = 2^{3a+1}\, 5^{3b+1}\, 11^{3c+1} \prod p_i^{3e_i},$
so its divisor count is
$(3a+2)(3b+2)(3c+2)\prod (3e_i + 1) = 110 = 2\cdot 5\cdot 11.$

Each of the three factors $3a+2$ , $3b+2$ , $3c+2$ is at least $2$ , so their product is at least $8$ ; the leftover $\prod(3e_i+1)$ must then be a divisor of $110$ that is at most $13$ and is $1$ more than a multiple of $3$ . The candidates $1, 10$ fail unless the product is $1$ (with $10$ the remaining product would be $11$ , too small to be a product of three numbers each at least $2$ ). So $k = 1$ and $\{3a+2, 3b+2, 3c+2\} = \{2, 5, 11\}$ , i.e. $\{a, b, c\} = \{0, 1, 3\}$ in some order.

Thus $n = p\, q^3$ for two distinct primes $p, q \in \{2, 5, 11\}$ , and neither is $3$ . Then
$81 n^4 = 3^4\, p^4\, q^{12},$
which has $(4+1)(4+1)(12+1) = 5\cdot 5\cdot 13 = 325$ divisors, regardless of which primes play the roles of $p$ and $q$ .

The answer is $\boxed{\textbf{(D)}\ 325}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.2, §4.4)