AMC 10 · 2013 · #9

Grade 8 number-theory

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

factoriallegendre-formulaprime-factorizationperfect-squaresexponents extremal-constructionconvert-to-algebra ↑ Prerequisites: prime-factorizationfactorial

📏 Long solution 💡 3 insights

Problem

The largest perfect-square divisor of a factorial is taken and its root examined. Add the root's prime exponents.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Extreme Principle

12! is a nine-digit number, so hunting for its largest square divisor by trial is hopeless. Switch coordinates: describe every divisor by its list of prime exponents. In those coordinates, dividing 12! means 'each exponent is small enough' and being a perfect square means 'each exponent is even', so the two conditions never fight each other. That lets each prime be pushed to its own maximum separately, and the separate maxima combine into one number that beats every competitor at once. The last step is bookkeeping: halve the exponents for the square root and add them.

1STEP 1

Switch to exponent coordinates

Exponent coordinates describe every divisor.

12! = 2^e₂ · 3^e₃ · 5^e₅ · 7^e₇ · 11^e₁₁, d = 2^a₂ · 3^a₃ · 5^a₅ · 7^a₇ · 11^a₁₁

2STEP 2

Count each prime by counting multiples

Counting multiples gives each prime's exponent.

e₂=⌊12/2⌋+⌊12/4⌋+⌊12/8⌋=6+3+1=10, e₃=⌊12/3⌋+⌊12/9⌋=4+1=5, e₅=2, e₇=1, e₁₁=1

3STEP 3

Write both conditions as exponent rules

Both conditions become plain exponent rules.

d ∣ 12! ⇔ a_p ≤ e_p for every p; d = m² ⇔ a_p is even for every p

4STEP 4

Push each prime to its own maximum

Each prime pushes to its own maximum.

N = 2¹⁰ · 3⁴ · 5² = (2⁵ · 3² · 5)² = 1440² = 2073600

5STEP 5

Show nothing else can beat N

Nothing else can beat that choice.

a_p even and a_p ≤ e_p ⟹ a_p ≤ 2⌊e_p/2⌋ ⟹ d ∣ N ⟹ d ≤ N

6STEP 6

Undo the squaring

Taking the root halves every exponent.

√(N) = √(2¹⁰ · 3⁴ · 5²) = 2⁵ · 3² · 5¹ = 1440

7STEP 7

Add the exponents

Adding them gives 8, choice (B).

5 + 2 + 1 = 8

Answer

Check the numbers directly. The prime count says 12! = 2¹0 * 3⁵ * 5² * 7 * 11, and multiplying that out gives 1024 * 243 * 25 * 77 = 479001600, which is 12!, so the exponents are right. Next, 1440² = 2073600 and 479001600 / 2073600 = 231 = 3 * 7 * 11. That leftover is squarefree, meaning no prime appears twice in it, so there is no extra square factor still waiting to be pulled out; the square part really has been taken as far as it goes. Finally sqrt(2073600) = 1440 = 2⁵ * 3² * 5¹ has exponent sum 5 + 2 + 1 = 8, choice (C). The size is also sane: the answer must be less than the exponent sum of 12! itself, which is 10 + 5 + 2 + 1 + 1 = 19, and roughly half of it, so 8 sits right where it should while 12 would be too large.

💡Key takeaway

Describe a number by its prime exponents, and then 'largest square divisor' just means making each exponent the biggest even number it is allowed to be.

Switch to exponent coordinates
Count each prime by counting multiples
Write both conditions as exponent rules
Push each prime to its own maximum
Show nothing else can beat N
Undo the squaring
Add the exponents