AMC 10 · 2020 · #21

Grade 8 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

prime-factorizationlcmgcdfactorialfundamental-counting-principle identify-subproblemscaseworksystematic-enumeration ↑ Prerequisites: prime-factorizationlcm

📏 Long solution 💡 3 insights

Problem

Count the positive integers that are multiples of 5 and satisfy this: the least common multiple of five factorial and the number equals five times the greatest common divisor of ten factorial and the number.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Identify Subproblems

Tool #15 (Organize Differently): rewrite the whole equation in terms of prime exponents. Once lcm becomes "take the max" and gcd becomes "take the min", one messy equation about huge numbers turns into a short list of tiny equations about small integers. Tool #4 (Introduce a Variable): name the exponents in n as a, b, c, d. Tool #7 (Subproblems): different primes never interact, so each prime becomes its own independent mini-problem, and the counts multiply. Tool #2 (Systematic List): for each prime, list exactly which exponent values survive.

1STEP 1

Factor both factorials

Write both as prime powers.

5! = 2³ · 3¹ · 5¹, 10! = 2⁸ · 3⁴ · 5² · 7¹

2STEP 2

Which primes are allowed

No other prime can appear.

n = 2^a · 3^b · 5^c · 7^d

3STEP 3

Turn it into exponents

Write both operations in exponents.

max(3, a) = min(8, a), max(1, b) = min(4, b), max(1, c) = min(2, c) + 1, max(0, d) = min(1, d)

4STEP 4

Solve for the prime two

That gives one range.

3 ≤ a ≤ 8 → a ∈ {3, 4, 5, 6, 7, 8}, 6 choices

5STEP 5

Solve for three and seven

Those two work the same way.

b ∈ {1, 2, 3, 4}, 4 choices; d ∈ {0, 1}, 2 choices

6STEP 6

Solve for the prime five

The exponent of five is forced.

c = 3, 1 choice

7STEP 7

Multiply the counts

Multiplying gives 48.

6 · 4 · 1 · 2 = 48 → (D)

Answer

Spot-check the smallest solution, (a, b, c, d) = (3, 1, 3, 0), i.e. n = 8 · 3 · 125 = 3000. Then lcm(120, 3000) = 3000, and gcd(3628800, 3000) = 600, and 5 · 600 = 3000. Equal, so it works. Spot-check the largest, (8, 4, 3, 1): n = 256 · 81 · 125 · 7 = 18144000, lcm(120, n) = n, gcd(10!, n) = 2⁸ · 3⁴ · 5² · 7 = 3628800, and 5 · 3628800 = 18144000. Equal. The count 48 = 6 · 4 · 1 · 2 also lines up with the trap choices: forgetting that the prime 7 contributes two options halves it to (B) 24, and stopping a at 5 instead of 8 gives 3 · 4 · 1 · 2 = 24 as well. The "multiple of 5" clause is not decoration: dropping it would admit c = 0 and double the answer to 96, which is not even a choice.

💡Key takeaway

Rewrite everything in prime exponents: lcm takes the bigger exponent, gcd takes the smaller one, so one huge equation splits into one tiny equation per prime — 6 ways for 2, 4 for 3, 1 for 5, 2 for 7, and 6 · 4 · 1 · 2 = 48.

Factor both factorials
Pin down which primes n can use
Turn the equation into exponents
Solve the prime-2 equation
Solve the prime-3 and prime-7 equations
Solve the prime-5 equation
Multiply the independent counts