AMC 10 · 2022 · #17

Grade 8 number-theory

Archetype Small-Domain Constrained Search

divisibility-rulesmodular-arithmeticexponentsprime-numberspolynomial-factoring pattern-recognitioneasier-related-problemcasework ↑ Prerequisites: modular-arithmeticprime-numbers

📏 Long solution 💡 3 insights

Problem

One of the following numbers is not divisible by any prime number less than $10.$ Which is it?

$\textbf{(A) } 2^{606}-1 \qquad\textbf{(B) } 2^{606}+1 \qquad\textbf{(C) } 2^{607}-1 \qquad\textbf{(D) } 2^{607}+1\qquad\textbf{(E) } 2^{607}+3^{607}$

Pick an answer.

(A)

$2^{606}-1$

(B)

$2^{606}+1$

(C)

$2^{607}-1$

(D)

$2^{607}+1$

(E)

$2^{607}+3^{607}$

View mode:

Toolkit + CCSS Solution

Understand

Restated: Among five expressions, exactly four are divisible by one of the primes $\{2, 3, 5, 7\}$ and one isn't. Find the lone expression with no small prime factor.

Givens: Five candidates: $2^{606}-1,\ 2^{606}+1,\ 2^{607}-1,\ 2^{607}+1,\ 2^{607}+3^{607}$; Primes below $10$ are $2, 3, 5, 7$; Each candidate is odd (powers of $2$ are even; even $\pm 1$ is odd; even $+$ odd is odd), so divisibility by $2$ is ruled out automatically

Unknowns: Which of (A)–(E) is divisible by none of $2, 3, 5, 7$

Understand

Restated: Among five expressions, exactly four are divisible by one of the primes $\{2, 3, 5, 7\}$ and one isn't. Find the lone expression with no small prime factor.

Plan

Primary tool: #3 Eliminate Possibilities

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

Tool #3 (Eliminate): the five candidates are the universe; knock out any whose divisibility by $2, 3, 5,$ or $7$ is easy to spot. Tool #9 (Easier Problem): replace the exponent $607$ with $7$ first to see how $2^n + 1$ and $2^n - 1$ behave mod each small prime — the cycle pattern transfers. Tool #5 (Pattern): once we know $2 \bmod p$ cycles, the answer to "$2^{607} \bmod p$" is just "$607 \bmod (\text{cycle length})$" with table lookup. Four candidates fall to a one-line argument; verifying the survivor is the final step.

Execute — Answer: C

#3 Eliminate Possibilities 6.NS.B.4 Step 1

Knock out (A) $2^{606}-1$ with divisibility by $3$.
Since $2 \equiv -1 \pmod 3$, $2^{606} \equiv (-1)^{606} = 1$, so $2^{606} - 1 \equiv 0 \pmod 3$.

$$2^{606} - 1 \equiv 1 - 1 \equiv 0 \pmod 3$$

💡 $2 \equiv -1 \pmod 3$ turns the question into "is the exponent even?" — and $606$ is.

#3 Eliminate Possibilities 8.EE.A.1 Step 2

Knock out (D) $2^{607}+1$ with divisibility by $3$.
Same trick: $2^{607} \equiv (-1)^{607} = -1$, so $2^{607} + 1 \equiv -1 + 1 \equiv 0 \pmod 3$.
(Equivalently: $a^n + b^n$ is divisible by $a + b$ when $n$ is odd, and $2 + 1 = 3$.)

$$2^{607} + 1 \equiv -1 + 1 \equiv 0 \pmod 3$$

💡 Odd exponent flips $-1$ back to $-1$; adding $1$ kills it mod $3$.

#3 Eliminate Possibilities 8.EE.A.1 Step 3

Knock out (E) $2^{607}+3^{607}$ with divisibility by $5$.
The identity $a^n + b^n$ is divisible by $a + b$ when $n$ is odd.
Here $a = 2$, $b = 3$, $n = 607$ odd, and $a + b = 5$.

$$2^{607} + 3^{607} \equiv 0 \pmod 5$$

💡 Sum of two odd-power expressions is divisible by the sum of the bases.

#3 Eliminate Possibilities 8.EE.A.1 Step 4

Knock out (B) $2^{606}+1$ with divisibility by $5$.
Rewrite $2^{606} = (2^2)^{303} = 4^{303}$, so $2^{606} + 1 = 4^{303} + 1$.
Now $a = 4$, $b = 1$, $n = 303$ odd, $a + b = 5$, so $4^{303} + 1$ is divisible by $5$.

$$2^{606} + 1 = 4^{303} + 1^{303} \equiv 0 \pmod 5$$

💡 Group the exponent into pairs so the base becomes $4$; then $4 + 1 = 5$ does the work.

#3 Eliminate Possibilities 4.OA.B.4 Step 5

By elimination the answer is (C) $2^{607} - 1$.
Verify by checking each small prime separately.
Divisibility by $2$: $2^{607}$ is even, so $2^{607} - 1$ is odd — not divisible by $2$.

$2^{607} - 1$ is odd

💡 Even minus $1$ is odd.

#5 Look for a Pattern 6.NS.B.4 Step 6

Check $\bmod 3$ on (C).
$2 \equiv -1 \pmod 3$ and $607$ is odd, so $2^{607} \equiv -1$, giving $2^{607} - 1 \equiv -2 \equiv 1 \pmod 3$.

$$2^{607} - 1 \equiv -1 - 1 \equiv 1 \pmod 3$$

💡 Same $2 \equiv -1$ trick, but now the odd exponent leaves $-1$ behind, and $-1 - 1 = -2 \ne 0$ mod $3$.

#5 Look for a Pattern 6.NS.B.4 Step 7

Check $\bmod 5$.
The powers $2, 4, 8, 16 \equiv 2, 4, 3, 1 \pmod 5$ — cycle of length $4$.
With $607 = 4 \cdot 151 + 3$, we get $2^{607} \equiv 2^3 = 8 \equiv 3 \pmod 5$, so $2^{607} - 1 \equiv 2 \pmod 5$ — not divisible.

$$607 \bmod 4 = 3 \Rightarrow 2^{607} \equiv 3 \Rightarrow 2^{607} - 1 \equiv 2 \pmod 5$$

💡 $2 \bmod 5$ cycles every $4$ steps; line up $607$ with the cycle position.

#5 Look for a Pattern 6.NS.B.4 Step 8

Check $\bmod 7$.
The powers $2, 4, 8 \equiv 2, 4, 1 \pmod 7$ — cycle of length $3$.
With $607 = 3 \cdot 202 + 1$, we get $2^{607} \equiv 2^1 = 2 \pmod 7$, so $2^{607} - 1 \equiv 1 \pmod 7$ — not divisible.
So (C) survives every test.
Answer: $\textbf{(C)}\ 2^{607} - 1$.

$$607 \bmod 3 = 1 \Rightarrow 2^{607} \equiv 2 \Rightarrow 2^{607} - 1 \equiv 1 \pmod 7$$

💡 Same cycle move, length $3$ this time.

[1] #3 6.NS.B.4 Knock out (A) $2^{606}-1$ with divisibility by $3$. Since $2 \equiv -1 \pmod 3$,

[2] #3 8.EE.A.1 Knock out (D) $2^{607}+1$ with divisibility by $3$. Same trick: $2^{607} \equiv

[3] #3 8.EE.A.1 Knock out (E) $2^{607}+3^{607}$ with divisibility by $5$. The identity $a^n + b^

[4] #3 8.EE.A.1 Knock out (B) $2^{606}+1$ with divisibility by $5$. Rewrite $2^{606} = (2^2)^{30

[5] #3 4.OA.B.4 By elimination the answer is (C) $2^{607} - 1$. Verify by checking each small pr

[6] #5 6.NS.B.4 Check $\bmod 3$ on (C). $2 \equiv -1 \pmod 3$ and $607$ is odd, so $2^{607} \equ

[7] #5 6.NS.B.4 Check $\bmod 5$. The powers $2, 4, 8, 16 \equiv 2, 4, 3, 1 \pmod 5$ — cycle of l

[8] #5 6.NS.B.4 Check $\bmod 7$. The powers $2, 4, 8 \equiv 2, 4, 1 \pmod 7$ — cycle of length $

Review

Reasonableness: Four candidates were killed by clean one-line arguments (mod $3$ twice, mod $5$ twice). The lone survivor (C) passed independent checks against all four small primes. Trivia: $2^{607} - 1$ is in fact a Mersenne prime (its smallest prime factor is itself), but we did not need that — we only needed "no small prime factor."

Alternative: Tool #9 (Easier Problem) standalone: replace exponents $606, 607$ with $6, 7$ and tabulate $2^6 - 1 = 63 = 9 \cdot 7$ (kills mod 3 and 7), $2^6 + 1 = 65 = 5 \cdot 13$ (mod 5), $2^7 - 1 = 127$ (prime — no small factor!), $2^7 + 1 = 129 = 3 \cdot 43$, $2^7 + 3^7 = 128 + 2187 = 2315 = 5 \cdot 463$. The exponent-$7$ table already says: option (C) wins. The full exponent-$607$ argument is just the same pattern at scale.

CCSS standards used (min grade 8)

6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Mod-arithmetic divisibility checks for primes $3$, $5$, $7$ using cycle reasoning of powers of $2$.)
8.EE.A.1 Know and apply the properties of integer exponents (Rewriting $2^{606} = 4^{303}$ and using the identity $a^n + b^n$ divisible by $a + b$ for odd $n$.)
4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Confirming that $2^{607}$ is even, so $2^{607} - 1$ is odd (not divisible by $2$).)

⭐ Four of the five expressions are easy to kill: $a^n + b^n$ is divisible by $a + b$ when $n$ is odd, and $2 \equiv -1 \pmod 3$ handles the rest. The one survivor $2^{607} - 1$ avoids $2, 3, 5,$ and $7$ — choice $\textbf{(C)}$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 8)

More like this