2007 AMC 10A Problem 17

P16-20~3 minPrint

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

Suppose that $m$ and $n$ are positive integers such that $75m = n^{3}$ . What is the minimum possible value of $m + n$ ?

Show solution without answering

Key insight

75 is 3 times 5 times 5. To make a perfect cube, m must add two more 3s and one more 5, so m = 45 and n = 15.

Solution

A perfect cube, like $8 = 2 \times 2 \times 2$ or $216 = 2 \times 2 \times 2 \times 3 \times 3 \times 3$ , has each prime factor appearing a multiple of $3$ times. So look at the prime factors of $75$ .

1. Factor. $75 = 3 \times 5 \times 5$ . There is one $3$ and two $5$ s.
2. What is missing? To reach three of each, we need two more $3$ s and one more $5$ . So the smallest $m$ is
$m = 3 \times 3 \times 5 = 45.$
3. Check. $75 \times 45 = 3375 = 15 \times 15 \times 15$ . So $n = 15$ .
4. Sum. $m + n = 45 + 15 = 60$ .
5. Could a bigger $n$ give a smaller sum? No. Any $n$ that works must be a multiple of $15$ (it needs a $3$ and a $5$ ). If $n = 30$ , then $m = 30^3 \div 75 = 360$ , which is much bigger. Making $n$ bigger makes $m$ grow very fast, so the smallest choice wins.

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

Why this works

"Make this a perfect cube" is really about counting prime factors: each prime must show up a multiple of $3$ times. The smallest $m$ just fills in what is missing. Because $m$ grows like a cube as $n$ grows, the smallest $m$ also gives the smallest sum.

Concise solution

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

Factor: $75 = 3 \cdot 5^2$ . For $75m$ to be a perfect cube, every prime in its factorization must appear to a power divisible by $3$ . The prime $3$ currently has exponent $1$ , so $m$ must contribute at least $3^2$ ; the prime $5$ has exponent $2$ , so $m$ must contribute at least $5^1$ .

The smallest choice is $m = 3^2 \cdot 5 = 45$ , which gives $75 \cdot 45 = 3^3 \cdot 5^3 = 15^3$ , so $n = 15$ and $m + n = 60$ .

Could a larger $n$ give a smaller sum? Any valid $n$ must be divisible by $3$ and $5$ , so $n = 15k$ , and then $m = \frac{(15k)^3}{75} = 45k^3$ . The sum $45k^3 + 15k$ increases with $k$ , so $k = 1$ is optimal.

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

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Algebra, Chapter 20: Special Functions (§20.3)
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.2, §4.4)