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^{1002} - 4^{501}$ 의 약수가 되는 $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.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $10^{1002} - 4^{501}$을 나누는 가장 큰 $2$의 거듭제곱을 $2^{1002}$부터 $2^{1006}$ 중에서 찾아라.

주어진 것: 주어진 수는 $10^{1002} - 4^{501}$이다; $10 = 2 \cdot 5$이므로 $10^{1002} = 2^{1002} \cdot 5^{1002}$이다; $4 = 2^2$이므로 $4^{501} = 2^{1002}$이다; 선택지: (A) $2^{1002}$, (B) $2^{1003}$, (C) $2^{1004}$, (D) $2^{1005}$, (E) $2^{1006}$

구하는 것: 이 수를 나누는 가장 큰 인수 $2^{k}$에서 지수 $k$

이해

문제 재정리: $10^{1002} - 4^{501}$을 나누는 가장 큰 $2$의 거듭제곱을 $2^{1002}$부터 $2^{1006}$ 중에서 찾아라.

계획

주요 도구: #7 작은 문제로 쪼개기

보조 도구: #5 패턴 찾기, #9 더 쉬운 문제로 줄이기

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

실행 — 정답: D

#7 작은 문제로 쪼개기 8.EE.A.1 단계 1

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

각 조각을 밑 $2$로 다시 쓴다.
$10 = 2 \cdot 5$이므로 $1002$제곱하면 $10^{1002} = 2^{1002} \cdot 5^{1002}$이다.
$4 = 2^2$이므로 $4^{501} = (2^2)^{501} = 2^{1002}$이다.
이제 두 항이 모두 $2^{1002}$을 드러내고 있다.

$$10^{1002} = 2^{1002}\cdot 5^{1002}, \qquad 4^{501} = 2^{1002}$$

💡 두 수를 같은 밑 $2$로 맞추면 숨어 있던 $2$의 인수가 눈에 보인다.

#7 작은 문제로 쪼개기 6.EE.A.3 단계 2

공통인 2^1002 빼내기

두 항이 모두 $2^{1002}$을 가지므로 이를 빼낸다: $10^{1002} - 4^{501} = 2^{1002}\cdot 5^{1002} - 2^{1002} = 2^{1002}(5^{1002} - 1)$.
답은 $2^{1002}$에 $5^{1002} - 1$ 안에 들어 있는 여분의 $2$들을 곱한 것이다.
$5^{1002}$은 홀수이므로 $5^{1002}-1$은 짝수여서 적어도 하나는 더 있다.

$$10^{1002} - 4^{501} = 2^{1002}\,(5^{1002} - 1)$$

💡 공통 인수를 빼내면 무서운 수 하나가 익숙한 $2$의 거듭제곱 곱하기 작은 수수께끼로 바뀐다.

#7 작은 문제로 쪼개기 6.EE.A.3 단계 3

제곱의 차로 쪼개기

$5^{1002} = (5^{501})^2$로 쓰면 $5^{1002} - 1$은 제곱의 차이다: $5^{1002} - 1 = (5^{501} - 1)(5^{501} + 1)$.
$5^{501}$은 홀수이므로 두 인수 $5^{501}-1$과 $5^{501}+1$은 연속한 짝수이고, 따라서 각각 적어도 하나의 $2$를 가진다.

$$5^{1002} - 1 = (5^{501} - 1)(5^{501} + 1)$$

💡 연속한 두 짝수는 바로 이웃해 있어서 둘 중 하나만 $4$의 배수가 될 수 있다.

#5 패턴 찾기 4.OA.B.4 단계 4

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

$5$의 거듭제곱은 $4$로 나눈 나머지에 패턴이 있다.
$5 \equiv 1 \pmod 4$이므로 모든 거듭제곱이 $5^{501} \equiv 1 \pmod 4$을 만족한다.
그래서 $5^{501} + 1 \equiv 2 \pmod 4$이 되어 짝수이지만 $4$의 배수는 아니다 — $2$가 정확히 하나.
그리고 $5^{501} - 1 \equiv 0 \pmod 4$이므로 $4$의 배수 — $2$가 적어도 둘이다.

$$5^{501}+1 \equiv 2 \pmod 4, \qquad 5^{501}-1 \equiv 0 \pmod 4$$

💡 $5$의 모든 거듭제곱은 $4$의 배수보다 $1$ 크므로, $1$을 빼면 $4$의 배수에 닿고 $1$을 더하면 그보다 둘 더 간다.

#9 더 쉬운 문제로 줄이기 8.EE.A.1 단계 5

5^501 - 1을 정확히 못박기

$5^{501} - 1$ 안의 $2$ 개수를 인수분해로 정확히 센다: $5^{501} - 1 = (5 - 1)(5^{500} + 5^{499} + \cdots + 5 + 1) = 4 \cdot S$.
합 $S$는 $501$개의 항을 가지며 각 항이 $5$의 거듭제곱이라 홀수이다.
홀수 개의 홀수를 더하면 홀수이므로 $S$는 홀수이다.
따라서 $5^{501}-1 = 4 \times (\text{홀수})$는 정확히 $2$를 둘 가지고, $5^{501}+1$은 정확히 하나를 가진다.
합쳐서 $5^{1002}-1$은 $2 + 1 = 3$개의 $2$를 가진다.

$$5^{501}-1 = 4\,S,\ S\text{는 홀수} \;\Rightarrow\; v_2(5^{1002}-1) = 2 + 1 = 3$$

💡 남은 합이 홀수이므로 $2$들은 오직 앞에 깔끔하게 나온 $4$에서만 온다.

#7 작은 문제로 쪼개기 8.EE.A.1 단계 6

2의 거듭제곱 합치기

조각들을 다시 모은다: $10^{1002} - 4^{501} = 2^{1002}(5^{1002} - 1)$이고, $5^{1002}-1$은 $3$개의 $2$를 더 준다.
그래서 총합은 $2^{1002} \cdot 2^{3} = 2^{1005}$이고, 이보다 큰 $2$의 거듭제곱은 이 수를 나누지 못한다.
가장 큰 $2$의 거듭제곱은 $2^{1005}$, 즉 선택지 (D)이다.

$$2^{1002}\cdot 2^{3} = 2^{1005} \;\Rightarrow\; \textbf{(D)}$$

💡 같은 밑의 거듭제곱을 곱할 때 지수를 더하면 모든 $2$가 하나의 개수로 쌓인다.

[1] #7 8.EE.A.1 각 조각을 밑 $2$로 다시 쓴다. $10 = 2 \cdot 5$이므로 $1002$제곱하면 $10^{1002} = 2^{1002} \cdot 5

[2] #7 6.EE.A.3 두 항이 모두 $2^{1002}$을 가지므로 이를 빼낸다: $10^{1002} - 4^{501} = 2^{1002}\cdot 5^{1002} -

[3] #7 6.EE.A.3 $5^{1002} = (5^{501})^2$로 쓰면 $5^{1002} - 1$은 제곱의 차이다: $5^{1002} - 1 = (5^{501} -

[4] #5 4.OA.B.4 $5$의 거듭제곱은 $4$로 나눈 나머지에 패턴이 있다. $5 \equiv 1 \pmod 4$이므로 모든 거듭제곱이 $5^{501} \equiv

[5] #9 8.EE.A.1 $5^{501} - 1$ 안의 $2$ 개수를 인수분해로 정확히 센다: $5^{501} - 1 = (5 - 1)(5^{500} + 5^{499}

[6] #7 8.EE.A.1 조각들을 다시 모은다: $10^{1002} - 4^{501} = 2^{1002}(5^{1002} - 1)$이고, $5^{1002}-1$은 $3$

검토

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

대안 접근: 지수 올리기 보조정리(LTE)로 같은 개수를 한 줄에 얻는다: 짝수 지수 $n=1002$에 대해 $v_2(5^{n}-1) = v_2(5-1) + v_2(5+1) + v_2(n) - 1 = 2 + 1 + 1 - 1 = 3$. 여기에 빼낸 $2^{1002}$의 $1002$를 더하면 다시 $2^{1005}$이 되어 (D)를 확인한다.

사용된 CCSS 표준 (최저 학년 8)

8.EE.A.1 정수 지수의 성질을 알고 적용하여 동치인 수식을 만든다 ($10^{1002}=2^{1002}5^{1002}$과 $4^{501}=2^{1002}$로 고쳐 쓰고, 마지막에 $2^{1002}\cdot 2^3 = 2^{1005}$로 합치기.)
6.EE.A.3 연산의 성질을 적용하여 동치인 식을 만든다 (공통인 $2^{1002}$을 빼내고 $5^{1002}-1$을 제곱의 차 $(5^{501}-1)(5^{501}+1)$로 쪼개기.)
4.OA.B.4 약수와 배수를 찾고 자연수의 나누어떨어짐을 추론한다 ($5$의 거듭제곱을 $4$로 나눈 나머지로 어느 인수가 $4$의 배수이고 어느 것이 $2$를 하나만 갖는지 판단하기.)

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