AMC 10 · 2014 · #17

학년 8 number-theory

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

exponentsdifference-of-squaresmodular-arithmeticprime-factorization identify-subproblems ↑ 선수 지식: exponentsdifference-of-squares

📏 긴 풀이 💡 4 개 인사이트

문제

10¹⁰⁰² - 4⁵⁰¹을 나누는 가장 큰 2의 거듭제곱을 2¹⁰⁰²부터 2¹⁰⁰⁶ 중에서 찾아라.

답을 골라 클릭하세요.

(A)

$2^{1002}$

(B)

$2^{1003}$

(C)

$2^{1004}$

(D)

$2^{1005}$

(E)

$2^{1006}$

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

풀이 과정

전략 작은 문제로 쪼개기

수가 천문학적으로 크므로 도구 #7(작은 문제로 쪼개기)이 뼈대가 된다. 먼저 공통으로 들어 있는 2의 거듭제곱을 빼내면, 남은 한 인수 5¹⁰⁰² - 1 안에 숨은 2의 개수를 세는 문제로 줄어든다. 도구 #5(패턴 찾기)는 5의 거듭제곱을 4로 나눈 나머지를 읽어 어느 조각이 4의 배수이고 어느 조각이 2를 하나만 갖는지 알아낸다. 도구 #9(더 쉬운 문제로 줄이기)는 거대한 5¹⁰⁰²-1을 세기 쉬운 형태 (4 × 홀수)로 바꾼다.

1STEP 1

두 항을 2의 거듭제곱으로 쓰기

10 = 2 · 5이니 10¹⁰⁰² = 2¹⁰⁰² · 5¹⁰⁰², 4 = 2²이니 4⁵⁰¹ = (2²)⁵⁰¹. 두 항 모두 2¹⁰⁰²을 품는다.

10¹⁰⁰² = 2¹⁰⁰² · 5¹⁰⁰², 4⁵⁰¹ = 2¹⁰⁰²

2STEP 2

공통인 2¹002 빼내기

공통 인수를 빼내면 10¹⁰⁰² - 4⁵⁰¹ = 2¹⁰⁰²(5¹⁰⁰² - 1). 5¹⁰⁰²이 홀수라 남은 인수는 짝수다.

10¹⁰⁰² - 4⁵⁰¹ = 2¹⁰⁰² (5¹⁰⁰² - 1)

3STEP 3

제곱의 차로 쪼개기

5¹⁰⁰² = (5⁵⁰¹)²이니 5¹⁰⁰² - 1 = (5⁵⁰¹ - 1)(5⁵⁰¹ + 1), 연속한 두 짝수다.

5¹⁰⁰² - 1 = (5⁵⁰¹ - 1)(5⁵⁰¹ + 1)

4STEP 4

인수를 4로 나눈 나머지 읽기

5 ≡ 1 (mod 4)이니 5⁵⁰¹ + 1 ≡ 2 (mod 4)은 2를 정확히 하나, 5⁵⁰¹ - 1은 4의 배수다.

5⁵⁰¹+1 ≡ 2 (mod 4), 5⁵⁰¹-1 ≡ 0 (mod 4)

5STEP 5

5⁵01 - 1을 정확히 못박기

5⁵⁰¹ - 1 = 4 · S이고 홀수 501개의 합 S는 홀수라 2가 둘, 앞의 하나를 더해 3개다.

5⁵⁰¹-1 = 4 S, S는 홀수 → v₂(5¹⁰⁰²-1) = 2 + 1 = 3

6STEP 6

2의 거듭제곱 합치기

두 개수를 쌓으면 2¹⁰⁰² · 2³ = 2¹⁰⁰⁵, 더 큰 거듭제곱은 나누지 못한다 — 선택지 (D).

2¹⁰⁰² · 2³ = 2¹⁰⁰⁵ → (D)

정답

2¹⁰⁰⁵

출발점의 인수 2¹⁰⁰²은 이미 선택지 (A)와 같으므로 실제 답은 최소한 그만큼은 커야 한다. 5¹⁰⁰²-1에서 나온 여분의 세 2가 이를 2¹⁰⁰⁵까지 밀어 올리며, 이는 선택지 범위 2¹⁰⁰²부터 2¹⁰⁰⁶ 안에 편안히 들어간다. 개수 3이 믿을 만한 이유는 제곱의 차 각 인수를 정확히 못박았기 때문이다 — 5⁵⁰¹+1에서 2 하나, 5⁵⁰¹-1 = 4×홀수에서 정확히 둘 — 중복이나 누락이 없다.

💡핵심 정리

차에서 가장 큰 2의 거듭제곱을 찾으려면 먼저 공통 거듭제곱을 빼내고, 남은 2들을 인수별로 하나씩 세면 된다.

두 항을 2의 거듭제곱으로 쓰기
공통인 2¹002 빼내기
제곱의 차로 쪼개기
인수를 4로 나눈 나머지 읽기
5⁵01 - 1을 정확히 못박기
2의 거듭제곱 합치기