2021 AMC Fall 10B Problem 6

P1-10~3 minPrint

Divisibility & Factors Primes Set up the equation/formula and compute; no special trick needed Consider the largest/smallest element or boundary case

The least positive integer with exactly $2021$ distinct positive divisors can be written in the form $m \cdot 6^k$ , where $m$ and $k$ are integers and $6$ is not a divisor of $m$ . What is $m+k?$

Show solution without answering

Key insight

2021 = 43 times 47, so use exponents 46 and 42, the bigger one on 2. The number is 16 times 6 to the 42.

Solution

The divisor-counting rule. Take $12 = 2^2 \times 3^1$ . A divisor of $12$ picks how many $2$ s to use ( $0$ , $1$ , or $2$ : three choices) and how many $3$ s ( $0$ or $1$ : two choices). So $12$ has $3 \times 2 = 6$ divisors. In general, add $1$ to each exponent and multiply.

1. What exponents give 2021? Factor $2021 = 43 \times 47$ . Both $43$ and $47$ are prime, so $2021$ can only be written as a product of whole numbers bigger than $1$ in two ways: $2021$ by itself, or $43 \times 47$ .
- $2021$ by itself: one prime with exponent $2020$ , like $2^{2020}$ .
- $43 \times 47$ : two primes with exponents $42$ and $46$ .
2. Make the number small. Use the smallest primes, $2$ and $3$ . Put the bigger exponent on the smaller prime, since that costs less:
$2^{46} \times 3^{42}.$
This beats $2^{2020}$ easily: $3$ is less than $2^2$ , so $3^{42}$ is less than $2^{84}$ , and the whole number is less than $2^{46 + 84} = 2^{130}$ .
3. Put it in the form $m \times 6^k$ . Each pair of one $2$ and one $3$ makes a $6$ . There are $42$ threes, so pair them with $42$ of the twos. That leaves $46 - 42 = 4$ twos:
$2^{46} \times 3^{42} = 2^4 \times (2 \times 3)^{42} = 16 \times 6^{42}.$
4. Here $m = 16$ , which is not divisible by $6$ , and $k = 42$ . So $m + k = 16 + 42 = 58$ .

The answer is $\boxed{\textbf{(B)}\ 58}$ .

Why this works

The number of divisors depends only on the exponents, not on which primes you use. So "smallest number with this many divisors" has two steps: factor the divisor count to find the possible exponents, then give the biggest exponent to $2$ , the next to $3$ , and so on. Splitting into more small exponents almost always beats one huge exponent.

Concise solution

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

If $N = p_1^{e_1} p_2^{e_2} \cdots$ , the number of divisors is $(e_1 + 1)(e_2 + 1)\cdots$ . We need this product to equal $2021 = 43 \cdot 47$ .

Since $2021$ has only the factorizations $2021$ and $43 \cdot 47$ , either $N = p^{2020}$ or $N = p^{46} q^{42}$ for distinct primes $p, q$ . To make $N$ as small as possible, use the smallest primes and give the larger exponent to the smaller prime: the candidates are $2^{2020}$ and $2^{46} \cdot 3^{42}$ . The second is far smaller (it is less than $2^{46} \cdot 2^{84} = 2^{130}$ ).

Now write $2^{46} \cdot 3^{42}$ in the required form:
$2^{46} \cdot 3^{42} = 2^4 \cdot (2^{42} \cdot 3^{42}) = 16 \cdot 6^{42}.$
Here $m = 16$ is not divisible by $6$ and $k = 42$ , so $m + k = 16 + 42 = 58$ .

The answer is $\boxed{\textbf{(B)}\ 58}$ .

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)