AMC 10 · 2021 · #8

Grade 6 number-theory
Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint
lcmprime-factorizationexponentsdivisibility-rules identify-subproblemssystematic-enumeration ↑ Prerequisites: lcmprime-factorization
📏 Medium solution 💡 2 insights
Problem
Let the first number be the smallest that every integer from 10 to 30 divides. Then let the second be the smallest that the first and each of 32 through 40 divide. Find the second divided by the first.

Pick an answer.

(A)
1
(B)
2
(C)
37
(D)
74
(E)
2886
How to solve
Strategy Organize Information in More Ways

Written as ordinary digits, M and N are monstrous. But an LCM has a second, much friendlier form: a list of prime exponents. Rewriting both numbers that way (Organize Information in More Ways) turns the whole question into a comparison of exponents. That swap lets me solve an easier related problem — instead of finding N and M and dividing, I only hunt for the places where the exponent list changes. Then I split the hunt into nine tiny checks, one for each of 32 through 40 (Identify Subproblems). Eliminate Possibilities is kept in reserve as an independent check against the five answer choices.

1STEP 1

Read an LCM as a list of exponents

Read it as a list of exponents.

lcm(a₁, a₂, …, a_k) = Π_p prime p^ max_i v_p(a_i)
2STEP 2

Find the tallest prime tower in 10 to 30

Find the tallest tower in the first range.

M = 2⁴ · 3³ · 5² · 7 · 11 · 13 · 17 · 19 · 23 · 29
3STEP 3

Compare exponents instead of dividing

Compare exponents instead of dividing.

N/M = Π_p prime p^ v_p(N) - v_p(M)
4STEP 4

Check 32 through 40 one at a time

Most new numbers are already covered.

32 = 2⁵, 33 = 3 · 11, 34 = 2 · 17, 35 = 5 · 7, 36 = 2² · 3², 37, 38 = 2 · 19, 39 = 3 · 13, 40 = 2³ · 5
5STEP 5

Multiply the two changes

Multiplying the two changes gives 74.

N/M = 2⁵⁻⁴ · 37¹⁻⁰ = 2 · 37 = 74
Answer
74
Check that 74M really is a common multiple of 32 through 40. Since 74M = 2 · 37 · M = 2⁵ · 3³ · 5² · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 37, it holds 2⁵ for 32, 2² · 3² for 36, 2³ · 5 for 40, and 37 itself — every requirement is met. It also cannot be any smaller: 37 is prime and divides N but not M, so 37 must divide N/M; and 2⁵ divides N while only 2⁴ divides M, so a factor of 2 must also survive. That forces N/M to be at least 2 · 37 = 74, and it is exactly 74. Note the problem quietly skips 31; if 31 had been on the list, the ratio would have picked up another prime factor.
💡Key takeaway

An LCM is really just a list of the biggest prime powers, so comparing two LCMs means comparing exponents — never multiplying out the giant numbers.

  • Read an LCM as a list of exponents
  • Find the tallest prime tower in 10 to 30
  • Compare exponents instead of dividing
  • Check 32 through 40 one at a time
  • Multiply the two changes

More like this

Same archetype — closest grade level first.