2022 AMC 10B Problem 17

The primes less than $10$ are $2, 3, 5, 7$. Every choice is odd (a power of $2$ is even, and adding or subtracting an odd number makes it odd), so $2$ never divides them. We only need to test $3$, $5$ and $7$. It is easier to find factors in four choices than to prove none in one, so knock out four.

1. (A) $2^{606} - 1$. Write $2^{606} = 4^{303}$. The powers of $4$ are $4, 16, 64, \ldots$, and each one is $1$ more than a multiple of $3$ ($4 = 3 + 1$, $16 = 15 + 1$, $64 = 63 + 1$). So $4^{303} - 1$ is a multiple of $3$.
2. (B) $2^{606} + 1$. Again $2^{606} = 4^{303}$. The last digits of powers of $4$ go $4, 6, 4, 6, \ldots$: $4$ for odd powers. Since $303$ is odd, $4^{303}$ ends in $4$, so $4^{303} + 1$ ends in $5$. It is a multiple of $5$.
3. (D) $2^{607} + 1$. Divide powers of $2$ by $3$: $2$ leaves $2$, $4$ leaves $1$, $8$ leaves $2$, $16$ leaves $1$, and so on. Odd powers leave remainder $2$. Since $607$ is odd, $2^{607} + 1$ leaves $2 + 1 = 3$, so it is a multiple of $3$.
4. (E) $2^{607} + 3^{607}$. Look at last digits. Powers of $2$ end in $2, 4, 8, 6$, repeating every $4$. Powers of $3$ end in $3, 9, 7, 1$, repeating every $4$. Since $607 = 4 \times 151 + 3$, we are at the 3rd spot: $2^{607}$ ends in $8$ and $3^{607}$ ends in $7$. The sum ends in $5$ ($8 + 7 = 15$), so it is a multiple of $5$.
5. Check (C) $2^{607} - 1$ to be sure.
- By $3$: $2^{607}$ leaves $2$ (odd power), so $2^{607} - 1$ leaves $1$. Not a multiple.
- By $5$: $2^{607}$ ends in $8$, so $2^{607} - 1$ ends in $7$. Not a multiple.
- By $7$: powers of $2$ divided by $7$ leave $2, 4, 1, 2, 4, 1, \ldots$, repeating every $3$. Since $607 = 3 \times 202 + 1$, $2^{607}$ leaves $2$, and $2^{607} - 1$ leaves $1$. Not a multiple.

So $2^{607} - 1$ has no prime factor less than $10$.

The answer is $\boxed{\textbf{(C)}\ 2^{607}-1}$.

Huge powers are never meant to be multiplied out. Their remainders and last digits repeat in short cycles, so you only need to know where the exponent falls in the cycle, and whether it is odd or even. When a question says "exactly one choice has this property", it is often quicker to show the other four fail.

Factoring rules give the same eliminations. For any whole number $n$, $a - b$ divides $a^n - b^n$; and when $n$ is odd, $a + b$ divides $a^n + b^n$. So $4 - 1 = 3$ divides $4^{303} - 1$ (A), $4 + 1 = 5$ divides $4^{303} + 1$ (B), $2 + 1 = 3$ divides $2^{607} + 1$ (D), and $2 + 3 = 5$ divides $2^{607} + 3^{607}$ (E).

The primes less than $10$ are $2, 3, 5, 7$. All five numbers are odd, so we look for factors of $3$, $5$ or $7$ using two facts: $a - b$ divides $a^n - b^n$ for every $n$, and $a + b$ divides $a^n + b^n$ when $n$ is odd.

• (A) $2^{606} - 1 = 4^{303} - 1$ is divisible by $4 - 1 = 3$.
• (B) $2^{606} + 1 = 4^{303} + 1$, and $303$ is odd, so it is divisible by $4 + 1 = 5$.
• (D) $2^{607} + 1$ with $607$ odd is divisible by $2 + 1 = 3$.
• (E) $2^{607} + 3^{607}$ with $607$ odd is divisible by $2 + 3 = 5$.

That leaves (C). To confirm, check $2^{607} - 1$ directly. Mod $3$: $2 \equiv -1$, so $2^{607} - 1 \equiv -1 - 1 \equiv 1$. Mod $5$: $2^4 \equiv 1$ and $607 = 4 \cdot 151 + 3$, so $2^{607} \equiv 2^3 = 8 \equiv 3$ and $2^{607} - 1 \equiv 2$. Mod $7$: $2^3 \equiv 1$ and $607 = 3 \cdot 202 + 1$, so $2^{607} - 1 \equiv 2 - 1 = 1$. None of $3, 5, 7$ divides it, and it is odd.

The answer is $\boxed{\textbf{(C)}\ 2^{607}-1}$.