AMC 10 · 2022 · #15

학년 8 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

divisibility-rulesmodular-arithmeticexponentsprime-numberspolynomial-factoring pattern-recognitioneasier-related-problemcasework ↑ 선수 지식: modular-arithmeticprime-numbers

📏 긴 풀이 💡 3 개 인사이트

문제

다섯 개의 식 중에서 정확히 넷은 2, 3, 5, 7 중 어떤 소수로 나누어떨어지고 하나는 그렇지 않습니다. 작은 소인수가 없는 그 하나를 찾으세요.

답을 골라 클릭하세요.

(A)

$2^{606}-1$

(B)

$2^{606}+1$

(C)

$2^{607}-1$

(D)

$2^{607}+1$

(E)

$2^{607}+3^{607}$

풀이 과정

전략 가능성 지우기

도구 #3 (지우기): 다섯 후보가 우주, 2, 3, 5, 7 중 하나로 잘 나누어 떨어지는 것부터 지웁니다. 도구 #9 (더 쉬운 문제): 지수를 607 대신 7로 바꿔 2ⁿ ± 1의 행동을 미리 관찰 — 같은 패턴이 큰 지수에서도 그대로 적용됩니다. 도구 #5 (패턴): 2 mod p 가 주기를 가지므로 "2⁶⁰⁷ mod p" 는 "607 mod (주기 길이)" 만 알면 표에서 바로 읽힙니다. 네 후보는 한 줄로 떨어지고, 남은 하나는 직접 검증.

1STEP 1

3으로 첫 식 지우기

3으로 나눈 나머지가 0입니다.

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

2STEP 2

3으로 둘째 식 지우기

둘째도 3으로 나누어떨어집니다.

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

3STEP 3

5로 셋째 식 지우기

셋째는 5로 나누어떨어집니다.

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

4STEP 4

5로 넷째 식 지우기

넷째도 5로 나누어떨어집니다.

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

5STEP 5

남은 식은 홀수

남은 식은 홀수입니다.

2⁶⁰⁷ - 1은 홀수

6STEP 6

3으로 확인하기

3으로도 나누어떨어지지 않습니다.

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

7STEP 7

5로 확인하기

주기를 써서 5도 확인합니다.

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

8STEP 8

7로 확인하기

7도 통과해 답은 2의 607제곱 빼기 1입니다.

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

정답

2⁶⁰⁷-1

네 후보는 한 줄짜리 깔끔한 논증으로 제거되었고 (mod 3 두 번, mod 5 두 번), 남은 (C)는 네 소수 각각에 대해 독립적으로 검증을 통과했습니다. 참고로 2⁶⁰⁷ - 1은 Mersenne 소수 (자기 자신이 가장 작은 소인수) — 다만 우리는 "작은 소인수가 없다" 만 보였으면 충분.

💡핵심 정리

다섯 후보 중 넷은 한 줄로 제거 — 홀수 n 에서 aⁿ + bⁿ 이 a + b 의 배수, 그리고 2 ≡ -1 (mod 3) 이라는 사실 두 가지면 충분. 살아남은 2⁶⁰⁷ - 1은 2, 3, 5, 7 어느 것으로도 나누어 떨어지지 않으니 답은 (C).