AMC 10 · 2020 · #22

Grade 8 number-theory

Archetype Arithmetic Expression Decomposition

polynomial-factoringsimons-favorite-factoring-trickmodular-arithmeticexponentsdifference-of-squares easier-related-problempattern-recognitionpolynomial-substitution ↑ Prerequisites: polynomial-factoringexponents

📏 Long solution 💡 3 insights

Problem

What is the remainder when $2^{202} +202$ is divided by $2^{101}+2^{51}+1$ ?

$\textbf{(A) } 100 \qquad\textbf{(B) } 101 \qquad\textbf{(C) } 200 \qquad\textbf{(D) } 201 \qquad\textbf{(E) } 202$

Pick an answer.

(A)

100

(B)

101

(C)

200

(D)

201

(E)

202

View mode:

Toolkit + CCSS Solution

Understand

Restated: Find the remainder when the huge number $2^{202} + 202$ is divided by $2^{101} + 2^{51} + 1$.

Givens: Dividend: $2^{202} + 202$; Divisor: $N = 2^{101} + 2^{51} + 1$; Answer choices: (A) $100$, (B) $101$, (C) $200$, (D) $201$, (E) $202$

Unknowns: The remainder $r$ such that $0 \le r < N$ and $2^{202} + 202 \equiv r \pmod{N}$

Understand

Restated: Find the remainder when the huge number $2^{202} + 202$ is divided by $2^{101} + 2^{51} + 1$.

Givens: Dividend: $2^{202} + 202$; Divisor: $N = 2^{101} + 2^{51} + 1$; Answer choices: (A) $100$, (B) $101$, (C) $200$, (D) $201$, (E) $202$

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #7 Identify Subproblems, #13 Convert to Algebra, #3 Eliminate Possibilities

Tool #9 (Easier Problem): replace $2^{50}$ by a single variable $x$. Then the divisor becomes $2x^2 + 2x + 1$ and the dividend $4x^4 + 202$ — much friendlier. Tool #5 (Pattern): recognize the Sophie Germain–style identity $4x^4 + 1 = (2x^2 + 2x + 1)(2x^2 - 2x + 1)$. Tool #7 (Subproblems): split $2^{202} + 202 = (2^{202} + 1) + 201$, dispose of the first piece via the identity, and read off the remainder. Tool #13 (Algebra): the algebraic identity is the engine. Tool #3 (Eliminate): the split $202 = 1 + 201$ already aligns with choice (D); other choices are sanity-killed.

Execute — Answer: D

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

Substitute $x = 2^{50}$.
Then $2^{100} = x^2$, $2^{101} = 2x^2$, $2^{51} = 2x$, and $2^{202} = 4x^4$.
The divisor becomes $N = 2x^2 + 2x + 1$, and the dividend $2^{202} + 202 = 4x^4 + 202$.

$$x = 2^{50}: \;\; N = 2x^2 + 2x + 1, \;\; \text{dividend} = 4x^4 + 202$$

💡 One letter replaces the huge $2^{50}$ — same problem, friendlier symbols.

#5 Look for a Pattern 8.EE.A.2 Step 2

Spot the Sophie Germain identity (a special case of difference-of-squares applied to $4x^4 + 1$): $$4x^4 + 1 \;=\; (2x^2)^2 + 2 \cdot (2x^2) \cdot 1 + 1 \;-\; (2x)^2 \;=\; (2x^2 + 1)^2 - (2x)^2.$$ Factor as a difference of squares: $$4x^4 + 1 \;=\; (2x^2 + 1 + 2x)(2x^2 + 1 - 2x) \;=\; (2x^2 + 2x + 1)(2x^2 - 2x + 1).$$

$$4x^4 + 1 = (2x^2 + 2x + 1)(2x^2 - 2x + 1)$$

💡 Complete the square: $4x^4 + 1 = (2x^2 + 1)^2 - (2x)^2$, then difference of squares.

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

So $4x^4 + 1 = N \cdot (2x^2 - 2x + 1)$, meaning $4x^4 + 1$ is divisible by $N = 2x^2 + 2x + 1$ exactly, with quotient $2x^2 - 2x + 1$ and remainder $0$.

$$4x^4 + 1 \;\equiv\; 0 \pmod{N}$$

💡 The Sophie Germain factorization shows $N$ divides $4x^4 + 1$ cleanly.

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

Now split the dividend: $4x^4 + 202 = (4x^4 + 1) + 201$.
The first piece is $\equiv 0 \pmod{N}$ by the previous step, so $$4x^4 + 202 \;\equiv\; 0 + 201 \;\equiv\; 201 \pmod{N}.$$

$$4x^4 + 202 \;\equiv\; 201 \pmod{N}$$

💡 Peel off the multiple of $N$; only the leftover $201$ remains.

#3 Eliminate Possibilities 6.NS.C.7 Step 5

Check that $201$ is a valid remainder (i.e., $0 \le 201 < N$).
Since $N = 2^{101} + 2^{51} + 1 > 2^{101} \approx 2.5 \times 10^{30}$, certainly $201 < N$.
So the remainder is exactly $201$, choice $(D)$.

$$r = 201 \Rightarrow \textbf{(D)}$$

💡 $201 \ll N$, so $201$ is the legitimate remainder.

[1] #9 8.EE.A.1 Substitute $x = 2^{50}$. Then $2^{100} = x^2$, $2^{101} = 2x^2$, $2^{51} = 2x$,

[2] #5 8.EE.A.2 Spot the Sophie Germain identity (a special case of difference-of-squares applie

[3] #7 6.EE.A.3 So $4x^4 + 1 = N \cdot (2x^2 - 2x + 1)$, meaning $4x^4 + 1$ is divisible by $N =

[4] #7 6.NS.B.4 Now split the dividend: $4x^4 + 202 = (4x^4 + 1) + 201$. The first piece is $\eq

[5] #3 6.NS.C.7 Check that $201$ is a valid remainder (i.e., $0 \le 201 < N$). Since $N = 2^{101

Review

Reasonableness: Sanity. The split $202 = 1 + 201$ is the giveaway: had the problem asked for $2^{202} + 100$, the answer would be $99$; for $+202$ it is $201$. We can also verify the factorization for a small case: try $x = 2$, so $4x^4 + 1 = 65$ and $(2x^2 + 2x + 1)(2x^2 - 2x + 1) = 13 \cdot 5 = 65$ ✓. The huge instance is the same algebraic identity, just with $x = 2^{50}$.

Alternative: Tool #13 (Convert to Algebra) directly via polynomial long division of $4x^4 + 202$ by $2x^2 + 2x + 1$: quotient is $2x^2 - 2x + 1$, remainder is $202 - 1 = 201$. Same answer, slightly more computation.

CCSS standards used (min grade 8)

6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Recognizing that one factor splits as a multiple of $N$ plus a small remainder.)
6.NS.C.7 Understand ordering and absolute value of rational numbers (Confirming $0 \le 201 < N$ so that $201$ is the standard non-negative remainder.)
6.EE.A.3 Apply the properties of operations to generate equivalent expressions (Rewriting $4x^4 + 202 = (4x^4 + 1) + 201$ and using divisibility of the first piece.)
8.EE.A.1 Know and apply the properties of integer exponents (Substituting $x = 2^{50}$ so that $2^{101} = 2x^2, 2^{51} = 2x, 2^{202} = 4x^4$.)
8.EE.A.2 Use square root and cube root symbols to represent solutions (Completing the square $4x^4 + 1 = (2x^2 + 1)^2 - (2x)^2$ and factoring as a difference of squares.)

⭐ This AMC 10 problem only needs the Grade 8 difference-of-squares trick — substitute $x = 2^{50}$ to turn the huge exponents into a small polynomial $4x^4 + 1 = (2x^2 + 2x + 1)(2x^2 - 2x + 1)$, then $2^{202} + 202 = (2^{202} + 1) + 201$ leaves remainder $201$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: D

Review

CCSS standards used (min grade 8)

More like this