AMC 10 · 2014 · #12

Grade 6 number-theory

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

prime-factorizationfactorsdivisor-count complementary-counting ↑ Prerequisites: prime-factorization

📏 Medium solution 💡 2 insights

Problem

The largest divisor of $2,014,000,000$ is itself. What is its fifth-largest divisor?

Pick an answer.

(A)

125, 875, 000

(B)

201, 400, 000

(C)

251, 750, 000

(D)

402, 800, 000

(E)

503, 500, 000

AMC 10 2014 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

Try it yourself first — the explanation is most useful after you’ve attempted it.

View mode:

Toolkit + CCSS Solution

Understand

Restated: The number $2{,}014{,}000{,}000$ has many whole-number divisors; its largest divisor is the number itself. Find its fifth-largest divisor.

Givens: $N = 2{,}014{,}000{,}000$; The largest divisor of $N$ is $N$ itself; Answer choices: (A) $125{,}875{,}000$, (B) $201{,}400{,}000$, (C) $251{,}750{,}000$, (D) $402{,}800{,}000$, (E) $503{,}500{,}000$

Unknowns: The fifth-largest divisor of $N$

Understand

Restated: The number $2{,}014{,}000{,}000$ has many whole-number divisors; its largest divisor is the number itself. Find its fifth-largest divisor.

Plan

Primary tool: #16 Change Focus / Count the Complement

Secondary: #7 Identify Subproblems, #2 Make a Systematic List

Listing the huge divisors of $N$ from the top down is painful. Tool #16 (Change Focus) flips the problem: every divisor $d$ of $N$ pairs with a partner $N/d$, and their product is $N$. As $d$ runs through the SMALLEST divisors $1, 2, 4, 5, \dots$, the partners $N/d$ run through the LARGEST divisors $N, N/2, N/4, \dots$ in matching order. So the fifth-largest divisor is just $N$ divided by the fifth-smallest divisor — a much easier target. Tool #7 (Identify Subproblems) handles the setup: prime-factor $N$ so we know exactly which small numbers divide it. Tool #2 (Systematic List) then walks the smallest divisors in order to find the fifth one, after which a single division finishes the job.

Execute — Answer: C

#16 Change Focus / Count the Complement 4.OA.B.4 Step 1

Flip largest to smallest

Divisors come in pairs: if $d$ divides $N$, then $N/d$ also divides $N$, and $d \cdot (N/d) = N$.
The smallest divisor $1$ pairs with the largest divisor $N$; the second-smallest divisor pairs with the second-largest; and so on.
So ranking divisors from the top is the same as ranking them from the bottom.
The fifth-largest divisor equals $N$ divided by the fifth-smallest divisor.

$$d \cdot \dfrac{N}{d} = N \;\Longrightarrow\; (\text{fifth-largest divisor}) = \dfrac{N}{(\text{fifth-smallest divisor})}$$

💡 Divisors line up in partner pairs that multiply to $N$, so counting down from the top mirrors counting up from the bottom.

#7 Identify Subproblems 5.NBT.A.2 Step 2

Split off the powers of ten

Write $N$ as a small number times a power of ten.
$2{,}014{,}000{,}000 = 2014 \times 1{,}000{,}000$, and the six trailing zeros mean $1{,}000{,}000 = 10^6 = (2 \cdot 5)^6 = 2^6 \cdot 5^6$.
Each zero contributes one factor of $2$ and one factor of $5$.

$$N = 2014 \times 10^6 = 2014 \times 2^6 \cdot 5^6$$

💡 Every trailing zero is one factor of $10 = 2 \times 5$, so six zeros hand you $2^6 \cdot 5^6$ for free.

#7 Identify Subproblems 6.NS.B.4 Step 3

Prime factorize N

Finish factoring by breaking down $2014$.
It is even: $2014 = 2 \cdot 1007$, and $1007 = 19 \cdot 53$ (both prime).
Combining with the powers of ten gives the full prime factorization of $N$.
The only prime bricks in $N$ are $2, 5, 19,$ and $53$; in particular $3$ and $7$ do NOT divide $N$.

$$N = 2 \cdot 19 \cdot 53 \cdot 2^6 \cdot 5^6 = 2^7 \cdot 5^6 \cdot 19 \cdot 53$$

💡 Once you know the prime bricks, you know exactly which small numbers are allowed to divide $N$.

#2 Make a Systematic List 4.OA.B.4 Step 4

List the five smallest divisors

Walk the whole numbers in order and keep the ones that divide $N$.
$1$ works.
$2$ works ($N$ is even).
$3$ fails (the digits $2{+}0{+}1{+}4 = 7$ are not a multiple of $3$).
$4 = 2^2$ works ($N$ has $2^7$).
$5$ works ($N$ ends in $0$).
$6 = 2\cdot 3$ fails (no factor of $3$), and $7$ fails (not a prime brick).
$8 = 2^3$ works.
So the smallest divisors in order are $1, 2, 4, 5, 8$, and the fifth-smallest is $8$.

$$1,\; 2,\; 4,\; 5,\; 8 \;\Rightarrow\; \text{fifth-smallest divisor} = 8$$

💡 Skip any number whose primes ($3$ or $7$) are missing from $N$, and the divisor ladder builds itself.

#7 Identify Subproblems 6.NS.B.2 Step 5

Divide N by 8

By the flip from Step 1, the fifth-largest divisor is $N \div 8$.
Dividing by $8 = 2^3$ just removes three factors of $2$: $N = 2^7 \cdot 5^6 \cdot 19 \cdot 53$ becomes $2^4 \cdot 5^6 \cdot 19 \cdot 53$.
Computing, $2^4 \cdot 5^6 = 16 \cdot 15625 = 250000$ and $19 \cdot 53 = 1007$, so the value is $250000 \cdot 1007 = 251{,}750{,}000$.
This matches choice (C).

$$\dfrac{N}{8} = \dfrac{2^7 \cdot 5^6 \cdot 19 \cdot 53}{2^3} = 2^4 \cdot 5^6 \cdot 19 \cdot 53 = 251{,}750{,}000 \;\Rightarrow\; \textbf{(C)}$$

💡 Dividing by $8$ simply peels off three of the $2$s in the factorization.

[1] #16 4.OA.B.4 Divisors come in pairs: if $d$ divides $N$, then $N/d$ also divides $N$, and $d

[2] #7 5.NBT.A.2 Write $N$ as a small number times a power of ten. $2{,}014{,}000{,}000 = 2014 \t

[3] #7 6.NS.B.4 Finish factoring by breaking down $2014$. It is even: $2014 = 2 \cdot 1007$, and

[4] #2 4.OA.B.4 Walk the whole numbers in order and keep the ones that divide $N$. $1$ works. $2

[5] #7 6.NS.B.2 By the flip from Step 1, the fifth-largest divisor is $N \div 8$. Dividing by $8

Review

Reasonableness: Listing the largest divisors from the top confirms the answer: $N$ (largest), then $N/2 = 1{,}007{,}000{,}000$, $N/4 = 503{,}500{,}000$ (choice E), $N/5 = 402{,}800{,}000$ (choice D), and $N/8 = 251{,}750{,}000$ (choice C). Notice choices (D) and (E) are the fourth- and third-largest divisors, so a hasty solver could slip into them — but the fifth-largest is (C). Multiplying back, $251{,}750{,}000 \times 8 = 2{,}014{,}000{,}000 = N$, so it truly is a divisor.

Alternative: List the largest divisors directly by dividing $N$ by its smallest divisors one at a time: $N/1, N/2, N/4, N/5, N/8$. The fourth of those uses divisor $5$ (since $3$ is skipped) and the fifth uses divisor $8$ (since $6$ and $7$ are skipped), landing on $N/8 = 251{,}750{,}000$. Same answer (C), reached without writing the full prime factorization.

CCSS standards used (min grade 6)

4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Using divisor pairs $d$ and $N/d$ to turn 'fifth-largest divisor' into 'N divided by the fifth-smallest divisor', and applying divisibility to build the list of smallest divisors.)
5.NBT.A.2 Explain patterns in number of zeros and placement of decimal point (Reading the six trailing zeros of $N$ as $10^6 = 2^6 \cdot 5^6$ to split $N = 2014 \times 10^6$.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Prime-factoring $N = 2^7 \cdot 5^6 \cdot 19 \cdot 53$ (via $2014 = 2 \cdot 19 \cdot 53$) to identify its prime bricks.)
6.NS.B.2 Fluently divide multi-digit numbers using the standard algorithm (Computing $N \div 8 = 251{,}750{,}000$ to get the fifth-largest divisor.)

⭐ The fifth-biggest divisor is just the number divided by the fifth-smallest divisor, because divisors always come in partner pairs that multiply to the whole.

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Flip largest to smallest

Split off the powers of ten

Prime factorize N

List the five smallest divisors

Divide N by 8

Review

CCSS standards used (min grade 6)

More like this