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: 2606≡1(mod3),2^{606} \equiv 1 \pmod 3, so 2606−12^{606} - 1 is divisible by 3.3. Option B: 2606≡4(mod5),2^{606} \equiv 4 \pmod 5, so 2606+12^{606} + 1 is divisible by 5.5. Option D: 2607≡2(mod3),2^{607} \equiv 2 \pmod 3, so 2607+12^{607} + 1 is divisible by 3.3. Option E: modulo 5,5, 2607+3607≡3+2=5≡0.2^{607} + 3^{607} \equiv 3 + 2 = 5 \equiv 0. For 2607−1:2^{607} - 1: it is ≡1(mod3),\equiv 1 \pmod 3, ≡2(mod5),\equiv 2 \pmod 5, and (since 23≡1(mod7)2^3 \equiv 1 \pmod 7 and 607≡1(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.
AoPS wiki

Tagged: modular arithmetic · multiplicative order · divisibility

More practice