AMC 10 · 2022 · #21

Grade 9 algebra

Archetype Modular Cycle Frequency Count └ Sub-archetype Power-Cycle Residue

polynomial-factoringpolynomial-substitutiondifference-of-cubesroots-of-unitymodular-arithmetic easier-related-problemconvert-to-algebrapattern-recognition ↑ Prerequisites: polynomial-factoring

📏 Long solution 💡 3 insights

Problem

A very high-degree polynomial is given. Among five listed polynomials, decide which one divides it exactly, leaving no remainder.

Pick an answer.

(A)

$x^2 -x + 1$

(B)

$x^2 + x + 1$

(C)

$x^4 + 1$

(D)

$x^6 - x^3 + 1$

(E)

$x^6 + x^3 + 1$

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Related Problem) — exponents of size 2022 are only scary if you treat them literally. Once a divisor forces powers to repeat in a short cycle, a huge exponent collapses to its remainder, and the problem shrinks to single-digit arithmetic. Tool #4 (Introduce a Variable) — both exponents are multiples of 3, so substituting u = x³ turns P into u⁶⁷⁴ + u³³⁷ + 1 and turns choice (E) into the very familiar u² + u + 1. Tool #5 (Look for a Pattern) — u² + u + 1 divides u³ - 1, which makes powers of u cycle with period 3. Tool #13 (Convert to Algebra) — turn the cycling observation into an explicit identity so the divisibility is proved, not just guessed. Tool #3 (Eliminate Possibilities) — a single numeric substitution x = 2 rules out the other four choices in one pass.

1STEP 1

Substitute to shrink the exponents

A substitution shrinks the exponents.

P(x) = (x³)⁶⁷⁴ + (x³)³³⁷ + 1 = u⁶⁷⁴ + u³³⁷ + 1, x⁶ + x³ + 1 = u² + u + 1

2STEP 2

Find the cycle length

Find the cycle length.

u³ - 1 = (u - 1)(u² + u + 1)

3STEP 3

Reduce 674 and 337 mod 3

Reduce the exponents modulo that cycle.

674 = 3 · 224 + 2, 337 = 3 · 112 + 1

4STEP 4

Make the division exact

Make the division exact.

u⁶⁷⁴ + u³³⁷ + 1 = (u² + u + 1) + u²(u⁶⁷² - 1) + u(u³³⁶ - 1)

5STEP 5

Spot-check with x = 2

Spot-check with one value.

P(2) mod 3 = 1, P(2) mod 7 = 3, P(2) mod 17 = 5, P(2) mod 57 = 16, P(2) mod 73 = 0

6STEP 6

Read off the answer

The answer is the sixth-degree factor.

x²⁰²² + x¹⁰¹¹ + 1 = (x⁶ + x³ + 1) · Q(x) → (E)

7STEP 7

Degree check on the cofactor

Check with a degree count.

(x¹⁰¹¹ - 1)P(x) = x³⁰³³ - 1, deg Q = 2022 - 6 = 2016

Answer

x⁶ + x³ + 1

The numeric test at x = 2 is decisive and easy to redo: 2⁶ + 2³ + 1 = 73, and 2⁹ = 512 = 7 · 73 + 1, so 2⁹ ≡ 1 (mod 73). Because 2022 = 9 · 224 + 6 and 1011 = 9 · 112 + 3, the giant number 2²⁰²² + 2¹⁰¹¹ + 1 leaves the same remainder as 2⁶ + 2³ + 1 = 73 ≡ 0. So 73 divides P(2) exactly — the divisibility is real, not an artifact of the algebra. Try x = 3 and the same thing happens: 3⁶ + 3³ + 1 = 757 and 3⁹ = 19683 = 26 · 757 + 1, so again P(3) ≡ 3⁶ + 3³ + 1 ≡ 0. Meanwhile every other choice failed at x = 2 with a nonzero remainder, and choice (B) fails in the most instructive way: x² + x + 1 makes x³ behave like 1, and since 3 divides both 2022 and 1011, P collapses to 1 + 1 + 1 = 3, never 0. The near-miss between (B) and (E) is the whole point of the problem.

💡Key takeaway

Exponents like 2022 stop being scary the moment you find the cycle: substitute u = x³, notice u² + u + 1 makes u³ act like 1, reduce 674 and 337 to remainders 2 and 1, and the giant polynomial collapses to u² + u + 1 = 0 — so x⁶ + x³ + 1 is the factor.

Substitute to shrink the exponents
Find the cycle length
Reduce 674 and 337 mod 3
Make the division exact
Spot-check with x = 2
Read off the answer
Degree check on the cofactor