경시 · AMC 대비 · 4단계 중 4

AMC 10 · 2022B · #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를 3으로 검사하기

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

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

2STEP 2

선택지 D를 3으로 검사하기

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

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

3STEP 3

선택지 E를 5로 검사하기

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

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

4STEP 4

선택지 B를 5로 검사하기

(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

C를 3으로 확인하기

(C)를 mod 3 검사: 607 홀수라 2⁶⁰⁷ ≡ -1, 따라서 2⁶⁰⁷-1 ≡ 1 — 안 나누어 떨어짐.

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

7STEP 7

C를 5로 확인하기

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

C를 7로 확인하기

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

선택지 A를 3으로 검사하기
선택지 D를 3으로 검사하기
선택지 E를 5로 검사하기
선택지 B를 5로 검사하기
남은 선택지 고르기
C를 3으로 확인하기
C를 5로 확인하기
C를 7로 확인하기

가족의 부모 대시보드는 sensimlab.com에 있습니다.