AMC 10 · 2022 · #17

Grade 8 number-theory

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

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

📏 Long solution 💡 3 insights

Problem

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.

Pick an answer.

(A)

$2^{606}-1$

(B)

$2^{606}+1$

(C)

$2^{607}-1$

(D)

$2^{607}+1$

(E)

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

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

How to solve

Strategy Eliminate Possibilities

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ⁿ + 1 and 2ⁿ - 1 behave mod each small prime — the cycle pattern transfers. Tool #5 (Pattern): once we know 2 mod p cycles, the answer to "2⁶⁰⁷ mod p" is just "607 mod (cycle length)" with table lookup. Four candidates fall to a one-line argument; verifying the survivor is the final step.

1STEP 1

(A) 2⁶⁰⁶-1 is divisible by 3: with 2 ≡ -1 mod 3 and 606 even, 2⁶⁰⁶ ≡ 1, so 2⁶⁰⁶-1 ≡ 0.

2⁶⁰⁶ - 1 ≡ 1 - 1 ≡ 0 (mod 3)

2STEP 2

(D) 2⁶⁰⁷+1 is divisible by 3: 607 is odd so aⁿ+bⁿ splits by a+b, and 2+1 = 3.

2⁶⁰⁷ + 1 ≡ -1 + 1 ≡ 0 (mod 3)

3STEP 3

(E) 2⁶⁰⁷+3⁶⁰⁷ is divisible by 5: the odd exponent makes aⁿ+bⁿ split by a+b, and 2+3 = 5.

2⁶⁰⁷ + 3⁶⁰⁷ ≡ 0 (mod 5)

4STEP 4

(B) 2⁶⁰⁶+1 is divisible by 5: rewrite as 4³⁰³+1 with odd 303, so 4+1 = 5 splits it.

2⁶⁰⁶ + 1 = 4³⁰³ + 1³⁰³ ≡ 0 (mod 5)

5STEP 5

By elimination only (C) 2⁶⁰⁷-1 is left; it is odd, so not divisible by 2.

2⁶⁰⁷ - 1 is odd

6STEP 6

Check (C) mod 3: 607 odd gives 2⁶⁰⁷ ≡ -1, so 2⁶⁰⁷-1 ≡ 1 — not divisible.

2⁶⁰⁷ - 1 ≡ -1 - 1 ≡ 1 (mod 3)

7STEP 7

Check mod 5: 2 cycles 2,4,3,1 (length 4); 607 ≡ 3, so 2⁶⁰⁷ ≡ 3 and 2⁶⁰⁷-1 ≡ 2.

607 mod 4 = 3 → 2⁶⁰⁷ ≡ 3 → 2⁶⁰⁷ - 1 ≡ 2 (mod 5)

8STEP 8

Check mod 7: 2 cycles 2,4,1 (length 3); 607 ≡ 1, so 2⁶⁰⁷ ≡ 2 and 2⁶⁰⁷-1 ≡ 1 — (C) wins.

607 mod 3 = 1 → 2⁶⁰⁷ ≡ 2 → 2⁶⁰⁷ - 1 ≡ 1 (mod 7)

Answer

2⁶⁰⁷-1

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⁶⁰⁷ - 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."

💡Key takeaway

Four of the five expressions are easy to kill: aⁿ + bⁿ is divisible by a + b when n is odd, and 2 ≡ -1 mod 3 handles the rest. The one survivor 2⁶⁰⁷ - 1 avoids 2, 3, 5, and 7 — choice (C).

More like this