Skip to main content

2022 AMC 12B Problem 15

Problem 15 of 25IntermediateNumber Theory

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

Answer choices

Show solution

Solution

Every option is odd, so only the primes 3,5,73, 5, 7 need checking. Option A: 26061(mod3),2^{606} \equiv 1 \pmod 3, so 260612^{606} - 1 is divisible by 3.3. Option B: 26064(mod5),2^{606} \equiv 4 \pmod 5, so 2606+12^{606} + 1 is divisible by 5.5. Option D: 26072(mod3),2^{607} \equiv 2 \pmod 3, so 2607+12^{607} + 1 is divisible by 3.3. Option E: modulo 5,5, 2607+36073+2=50.2^{607} + 3^{607} \equiv 3 + 2 = 5 \equiv 0. For 26071:2^{607} - 1: it is 1(mod3),\equiv 1 \pmod 3, 2(mod5),\equiv 2 \pmod 5, and (since 231(mod7)2^3 \equiv 1 \pmod 7 and 6071(mod3)607 \equiv 1 \pmod 3) 1(mod7).\equiv 1 \pmod 7. So it is not divisible by any prime below 10.10. Thus, the correct answer is C.

More practice

Concepts: modular arithmetic · multiplicative order · divisibility

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.