2022 AMC 12B Problem 15

Question

One of the following numbers is not divisible by any prime number less than

10.

Which is it?

2^{606} - 1

2^{606} + 1

2^{607} - 1

2^{607} + 1

2^{607} + 3^{607}

All five numbers are odd, so test divisibility only by

3, 5,

and

7

Use the cycles of

2^n

modulo

3, 5, 7:

for example

2^n \equiv 1 \pmod 3

when

n

is even

Every option is odd, so only the primes

3, 5, 7

need checking.

Option A:

2^{606} \equiv 1 \pmod 3,

so

2^{606} - 1

is divisible by

3.

Option B:

2^{606} \equiv 4 \pmod 5,

so

2^{606} + 1

is divisible by

5.

Option D:

2^{607} \equiv 2 \pmod 3,

so

2^{607} + 1

is divisible by

3.

Option E: modulo

5,

2^{607} + 3^{607} \equiv 3 + 2 = 5 \equiv 0.

For

2^{607} - 1:

it is

\equiv 1 \pmod 3,

\equiv 2 \pmod 5,

and (since

2^3 \equiv 1 \pmod 7

and

607 \equiv 1 \pmod 3

)

\equiv 1 \pmod 7.

So it is not divisible by any prime below

10.

Thus, the correct answer is C.

Problem 15 in other years