AMC 10 · 2022 · #17

학년 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}$

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 가능성 지우기

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

1STEP 1

(A) 2⁶⁰⁶-1 은 3 으로 나누어 떨어짐: 2 ≡ -1 (mod 3), 606 은 짝수라 2⁶⁰⁶ ≡ 1, 따라서 2⁶⁰⁶-1 ≡ 0.

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

2STEP 2

(D) 2⁶⁰⁷+1 은 3 으로 나누어 떨어짐: 607 이 홀수라 aⁿ+bⁿ 은 a+b 로 갈라지고 2+1 = 3.

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

3STEP 3

(E) 2⁶⁰⁷+3⁶⁰⁷ 은 5 로 나누어 떨어짐: 홀수 지수라 aⁿ+bⁿ 이 a+b 로 갈라지고 2+3 = 5.

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

4STEP 4

(B) 2⁶⁰⁶+1 은 5 로 나누어 떨어짐: 4³⁰³+1 로 바꾸면 303 이 홀수라 4+1 = 5 로 갈라짐.

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

5STEP 5

소거하면 (C) 2⁶⁰⁷-1 만 남고, 홀수라 2 로 나누어 떨어지지 않음.

2⁶⁰⁷ - 1 은 홀수

6STEP 6

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

7STEP 7

mod 5 검사: 2 의 거듭제곱 주기 2,4,3,1 (길이 4), 607 ≡ 3 이라 2⁶⁰⁷ ≡ 3, 2⁶⁰⁷-1 ≡ 2.

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

8STEP 8

mod 7 검사: 2 의 거듭제곱 주기 2,4,1 (길이 3), 607 ≡ 1 이라 2⁶⁰⁷ ≡ 2, 2⁶⁰⁷-1 ≡ 1 — (C) 확정.

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).

비슷한 유형 더 풀어보기