AMC 10 · 2014 · #17

Grade 8 number-theory

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

exponentsdifference-of-squaresmodular-arithmeticprime-factorization identify-subproblems ↑ Prerequisites: exponentsdifference-of-squares

📏 Long solution 💡 4 insights

Problem

What is the greatest power of $2$ that is a factor of $10^{1002} - 4^{501}$ ?

Pick an answer.

(A)

$2^{1002}$

(B)

$2^{1003}$

(C)

$2^{1004}$

(D)

$2^{1005}$

(E)

$2^{1006}$

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: Find the largest power of $2$ that divides the number $10^{1002} - 4^{501}$, choosing from $2^{1002}$ through $2^{1006}$.

Givens: The number is $10^{1002} - 4^{501}$; $10 = 2 \cdot 5$, so $10^{1002} = 2^{1002} \cdot 5^{1002}$; $4 = 2^2$, so $4^{501} = 2^{1002}$; Answer choices: (A) $2^{1002}$, (B) $2^{1003}$, (C) $2^{1004}$, (D) $2^{1005}$, (E) $2^{1006}$

Unknowns: The exponent $k$ in the greatest factor $2^{k}$ that divides the number

Understand

Restated: Find the largest power of $2$ that divides the number $10^{1002} - 4^{501}$, choosing from $2^{1002}$ through $2^{1006}$.

Plan

Primary tool: #7 Identify Subproblems

Secondary: #5 Look for a Pattern, #9 Solve an Easier Related Problem

The numbers are astronomically large, so Tool #7 (Identify Subproblems) is the spine: first pull out the obvious shared power of $2$, then the whole job shrinks to counting how many extra $2$s hide inside a single leftover factor $5^{1002} - 1$. Tool #5 (Look for a Pattern) reads the powers of $5$ modulo $4$ to see which pieces are divisible by $4$ and which carry only one $2$. Tool #9 (Solve an Easier Related Problem) replaces the giant $5^{1002}-1$ with a tiny factored form ($4 \times \text{odd}$) that is easy to count.

Execute — Answer: D

#7 Identify Subproblems 8.EE.A.1 Step 1

Write both terms as powers of 2

Rewrite each piece with base $2$.
Since $10 = 2 \cdot 5$, raising to the $1002$ gives $10^{1002} = 2^{1002} \cdot 5^{1002}$.
Since $4 = 2^2$, we get $4^{501} = (2^2)^{501} = 2^{1002}$.
Both terms now openly carry $2^{1002}$.

$$10^{1002} = 2^{1002}\cdot 5^{1002}, \qquad 4^{501} = 2^{1002}$$

💡 Putting both numbers over the same base $2$ makes the shared factors of $2$ visible instead of hidden.

#7 Identify Subproblems 6.EE.A.3 Step 2

Factor out the shared 2^1002

Both terms share $2^{1002}$, so factor it out: $10^{1002} - 4^{501} = 2^{1002}\cdot 5^{1002} - 2^{1002} = 2^{1002}(5^{1002} - 1)$.
The answer is $2^{1002}$ multiplied by whatever extra $2$s live inside $5^{1002} - 1$.
Since $5^{1002}$ is odd, $5^{1002}-1$ is even, so there is at least one more.

$$10^{1002} - 4^{501} = 2^{1002}\,(5^{1002} - 1)$$

💡 Pulling out the common factor turns one scary number into a known power of $2$ times a smaller mystery.

#7 Identify Subproblems 6.EE.A.3 Step 3

Split with difference of squares

Write $5^{1002} = (5^{501})^2$ so that $5^{1002} - 1$ is a difference of squares: $5^{1002} - 1 = (5^{501} - 1)(5^{501} + 1)$.
Because $5^{501}$ is odd, the two factors $5^{501}-1$ and $5^{501}+1$ are consecutive even numbers, so each contributes at least one factor of $2$.

$$5^{1002} - 1 = (5^{501} - 1)(5^{501} + 1)$$

💡 Two even numbers in a row always sit right next to each other, and only one of them can be a multiple of $4$.

#5 Look for a Pattern 4.OA.B.4 Step 4

Read the factors modulo 4

Powers of $5$ follow a pattern modulo $4$: since $5 \equiv 1 \pmod 4$, every power satisfies $5^{501} \equiv 1 \pmod 4$.
So $5^{501} + 1 \equiv 2 \pmod 4$, meaning it is even but not a multiple of $4$ — exactly one factor of $2$.
And $5^{501} - 1 \equiv 0 \pmod 4$, so it is a multiple of $4$ — at least two factors of $2$.

$$5^{501}+1 \equiv 2 \pmod 4, \qquad 5^{501}-1 \equiv 0 \pmod 4$$

💡 Every power of $5$ is one more than a multiple of $4$, so subtracting $1$ lands on a multiple of $4$ and adding $1$ lands two past it.

#9 Solve an Easier Related Problem 8.EE.A.1 Step 5

Pin down 5^501 - 1 exactly

Count the $2$s in $5^{501} - 1$ precisely by factoring: $5^{501} - 1 = (5 - 1)(5^{500} + 5^{499} + \cdots + 5 + 1) = 4 \cdot S$.
The sum $S$ has $501$ terms, each a power of $5$ and therefore odd; adding an odd count of odd numbers gives an odd total, so $S$ is odd.
Hence $5^{501}-1 = 4 \times (\text{odd})$ carries exactly two $2$s, and $5^{501}+1$ carries exactly one.
Together $5^{1002}-1$ carries $2 + 1 = 3$ factors of $2$.

$$5^{501}-1 = 4\,S,\ S\text{ odd} \;\Rightarrow\; v_2(5^{1002}-1) = 2 + 1 = 3$$

💡 The leftover sum is odd, so the only $2$s come from the clean factor of $4$ out front.

#7 Identify Subproblems 8.EE.A.1 Step 6

Combine the powers of 2

Bring the pieces back together: $10^{1002} - 4^{501} = 2^{1002}(5^{1002} - 1)$, and $5^{1002}-1$ supplies $3$ more factors of $2$.
So the total is $2^{1002} \cdot 2^{3} = 2^{1005}$, and no larger power of $2$ divides the number.
The greatest power of $2$ is $2^{1005}$, which is choice (D).

$$2^{1002}\cdot 2^{3} = 2^{1005} \;\Rightarrow\; \textbf{(D)}$$

💡 Adding exponents when multiplying powers of the same base stacks all the $2$s into one count.

[1] #7 8.EE.A.1 Rewrite each piece with base $2$. Since $10 = 2 \cdot 5$, raising to the $1002$

[2] #7 6.EE.A.3 Both terms share $2^{1002}$, so factor it out: $10^{1002} - 4^{501} = 2^{1002}\c

[3] #7 6.EE.A.3 Write $5^{1002} = (5^{501})^2$ so that $5^{1002} - 1$ is a difference of squares

[4] #5 4.OA.B.4 Powers of $5$ follow a pattern modulo $4$: since $5 \equiv 1 \pmod 4$, every pow

[5] #9 8.EE.A.1 Count the $2$s in $5^{501} - 1$ precisely by factoring: $5^{501} - 1 = (5 - 1)(5

[6] #7 8.EE.A.1 Bring the pieces back together: $10^{1002} - 4^{501} = 2^{1002}(5^{1002} - 1)$,

Review

Reasonableness: The starting factor $2^{1002}$ already matches choice (A), so the true answer must be at least that big; the extra three $2$s from $5^{1002}-1$ push it up to $2^{1005}$, comfortably inside the choice range $2^{1002}$ to $2^{1006}$. The count $3$ is trustworthy because each factor of the difference of squares was pinned exactly — one $2$ from $5^{501}+1$ and exactly two from $5^{501}-1 = 4\times\text{odd}$ — leaving no double counting or missed factor.

Alternative: The Lifting the Exponent lemma gives the same count in one line: for the even exponent $n=1002$, $v_2(5^{n}-1) = v_2(5-1) + v_2(5+1) + v_2(n) - 1 = 2 + 1 + 1 - 1 = 3$. Adding the $1002$ from the factored $2^{1002}$ again yields $2^{1005}$, confirming (D).

CCSS standards used (min grade 8)

8.EE.A.1 Know and apply the properties of integer exponents to generate equivalent numerical expressions (Rewriting $10^{1002}=2^{1002}5^{1002}$ and $4^{501}=2^{1002}$, and combining $2^{1002}\cdot 2^3 = 2^{1005}$ at the end.)
6.EE.A.3 Apply the properties of operations to generate equivalent expressions (Factoring out the common $2^{1002}$ and splitting $5^{1002}-1$ as a difference of squares $(5^{501}-1)(5^{501}+1)$.)
4.OA.B.4 Find factors and multiples and reason about divisibility of whole numbers (Deciding which factor is a multiple of $4$ and which carries only one factor of $2$ using powers of $5$ modulo $4$.)

⭐ To find the biggest power of $2$ hiding in a difference, pull out the shared power first, then count the leftover $2$s one factor at a time.

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: D

Write both terms as powers of 2

Factor out the shared 2^1002

Split with difference of squares

Read the factors modulo 4

Pin down 5^501 - 1 exactly

Combine the powers of 2

Review

CCSS standards used (min grade 8)

More like this