2005 AMC 10A Problem 15

P11-15~4 minPrint

Divisibility & Factors Primes Set up the equation/formula and compute; no special trick needed

How many positive cubes divide $3! \cdot 5! \cdot 7!$ ?

Show solution without answering

Key insight

Write the product as 2^8 times 3^4 times 5^2 times 7. A cube divisor uses each prime a multiple of 3 times, giving 3 times 2 choices.

Solution

Questions about divisors are easiest with prime factorizations, so factor everything first.

1. Factor each factorial.
- $3! = 6 = 2 \cdot 3$
- $5! = 120 = 2^3 \cdot 3 \cdot 5$
- $7! = 5040 = 2^4 \cdot 3^2 \cdot 5 \cdot 7$
2. Multiply by adding exponents. Twos: $1 + 3 + 4 = 8$ . Threes: $1 + 1 + 2 = 4$ . Fives: $1 + 1 = 2$ . Sevens: $1$ .
$3! \cdot 5! \cdot 7! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7.$
3. What does a cube divisor look like? A divisor uses each prime at most as many times as the product has it. It is a perfect cube when each prime appears $0, 3, 6, \ldots$ times.
4. Choices for each prime.
- Two: $0$ , $3$ or $6$ times (not $9$ , since only $8$ are available): $3$ choices.
- Three: $0$ or $3$ times: $2$ choices.
- Five: only $2$ available, so $0$ times: $1$ choice.
- Seven: only $1$ available, so $0$ times: $1$ choice.
5. Multiply the choices. $3 \times 2 \times 1 \times 1 = 6$ .

The six cubes are $1, 8, 27, 64, 216, 1728$ .

The answer is $\boxed{\textbf{(E)}\ 6}$ .

Why this works

Every divisor is built by choosing how many of each prime to use, up to what is available. A perfect cube needs each count to be a multiple of $3$ , and $0$ counts too. Count the allowed choices prime by prime and multiply. The same method counts square divisors (use multiples of $2$ ).

Concise solution

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

Factor each factorial: $3! = 2 \cdot 3$ , $5! = 2^3 \cdot 3 \cdot 5$ , $7! = 2^4 \cdot 3^2 \cdot 5 \cdot 7$ . Multiplying and adding exponents,
$3! \cdot 5! \cdot 7! = 2^{8} \cdot 3^{4} \cdot 5^{2} \cdot 7.$

A divisor $2^a 3^b 5^c 7^d$ is a perfect cube exactly when every exponent is a multiple of $3$ , and it divides the product when $a \leq 8$ , $b \leq 4$ , $c \leq 2$ , $d \leq 1$ . The options:

$a \in \{0, 3, 6\}$ : $3$ choices,
$b \in \{0, 3\}$ : $2$ choices,
$c = 0$ and $d = 0$ : $1$ choice each.

By the multiplication principle there are $3 \cdot 2 \cdot 1 \cdot 1 = 6$ cube divisors, namely $1, 8, 27, 64, 216, 1728$ .

The answer is $\boxed{\textbf{(E)}\ 6}$ .

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)