AMC 10 · 2022 · #15

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 two, three, five, and seven, and one is not. 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}$

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

Kill the first with three

It is zero modulo three.

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

2STEP 2

Kill the second with three

The second is also divisible by three.

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

3STEP 3

Kill the third with five

The third is divisible by five.

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

4STEP 4

Kill the fourth with five

The fourth is also divisible by five.

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

5STEP 5

The survivor is odd

The survivor is odd.

2⁶⁰⁷ - 1 is odd

6STEP 6

Check it against three

It is not divisible by three either.

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

7STEP 7

Check it against five

Use the cycle to check five.

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

8STEP 8

Check it against seven

Seven passes too, so it is two to the six hundred seventh minus one.

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).