AMC 10 · 2009 · #21

학년 4 number-theory

유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue

modular-arithmeticexponentspattern-recognition pattern-recognition ↑ 선수 지식: modular-arithmetic

📏 중간 풀이 💡 2 개 인사이트

📘 쉬운 버전 보기 →

문제

$3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$ 을 8로 나눈 나머지는 얼마인가?

답을 골라 클릭하세요.

(A)

$\ 0$

(B)

$\ 1$

(C)

$\ 2$

(D)

$\ 4$

(E)

$\ 6$

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $3^0$부터 $3^{2009}$까지 $3$의 거듭제곱을 모두 더한 뒤, 그 커다란 합을 $8$로 나눈다. 나머지를 구하라.

주어진 것: 합은 $3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$ 이다; 지수가 $0$부터 $2009$까지이므로 항은 모두 $2010$개다; 이 합 전체를 $8$로 나눈다

구하는 것: 합을 $8$로 나눈 나머지

이해

문제 재정리: $3^0$부터 $3^{2009}$까지 $3$의 거듭제곱을 모두 더한 뒤, 그 커다란 합을 $8$로 나눈다. 나머지를 구하라.

주어진 것: 합은 $3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$ 이다; 지수가 $0$부터 $2009$까지이므로 항은 모두 $2010$개다; 이 합 전체를 $8$로 나눈다

계획

주요 도구: #5 패턴 찾기

보조 도구: #9 더 쉬운 문제로 줄이기, #7 작은 문제로 쪼개기, #3 가능성 지우기

합이 너무 커서 그대로 더할 수 없으므로, 도구 #9(더 쉬운 문제로 줄이기)로 크기를 줄인다. 합을 $8$로 나눈 나머지는 각 항의 나머지에만 좌우되므로, 각 거듭제곱 $3^k$을 작은 나머지로 바꾼다. 도구 #5(패턴 찾기)가 핵심 엔진이다. $3^0,3^1,3^2,\ldots$의 나머지는 커지지 않고 짧은 주기로 반복되므로, 거대한 수를 건드릴 필요가 없다. 도구 #7(작은 문제로 쪼개기)은 "나머지 $2010$개 더하기"를 둘씩 짝짓는 쉬운 작은 문제로 바꾸고, 도구 #3(가능성 지우기)은 마지막 나머지를 보기 다섯 개 중 하나에 맞춘다.

실행 — 정답: D

#5 패턴 찾기 4.OA.C.5 단계 1

나머지 주기 찾기

$3$의 거듭제곱을 $8$로 나눈 나머지를 나열한다.
$3^0=1$은 나머지 $1$, $3^1=3$은 나머지 $3$, $3^2=9=8+1$은 나머지 $1$, $3^3=27=24+3$은 나머지 $3$이다.
$3^2$에서 나머지가 다시 $1$로 돌아오므로 그 뒤로는 계속 반복된다.
나머지는 $1,3,1,3,1,3,\ldots$으로 길이 $2$의 주기를 이룬다.
짝수 지수는 나머지 $1$, 홀수 지수는 나머지 $3$이다.

$$3^0,3^1,3^2,3^3,\ldots \equiv 1,3,1,3,\ldots \pmod 8$$

💡 나머지가 한 번 반복되면 목록 전체가 순환하므로, 거대한 거듭제곱 대신 짧은 주기만 알면 된다.

#9 더 쉬운 문제로 줄이기 3.OA.B.5 단계 2

각 거듭제곱을 나머지로 바꾸기

합을 $8$로 나눈 나머지는 각 조각의 나머지로 정해진다.
작은 나머지들을 더한 뒤 그 합의 나머지를 구하면 된다.
그래서 실제 합 대신, 각 항의 나머지 $1+3+1+3+\cdots$을 $2010$개 더한다.
덧셈은 순서와 묶음을 바꿔도 나머지가 변하지 않으므로 이 바꾸기는 정당하다.

$$\left(3^0+\cdots+3^{2009}\right)\bmod 8 = \left(\underbrace{1+3+1+3+\cdots}_{2010\text{개 항}}\right)\bmod 8$$

💡 나머지는 수 그 자체처럼 더해지므로, 복잡한 합과 깔끔한 나머지 합은 같은 나머지를 남긴다.

#7 작은 문제로 쪼개기 4.NBT.B.5 단계 3

짝지어 합산하기

나머지를 둘씩 묶는다.
$(1+3)$, 또 $(1+3)$, 이런 식이다.
각 짝의 합은 $4$이다.
항이 $2010$개이므로 $2010\div 2 = 1005$개의 짝이 된다.
따라서 나머지 전체 합은 $4$가 $1005$번, 즉 $1005\times 4 = 4020$이다.

$$1005\times(1+3)=1005\times 4 = 4020$$

💡 반복되는 주기를 똑같은 짝으로 묶으면 긴 덧셈이 곱셈 하나로 바뀐다.

#3 가능성 지우기 4.NBT.B.6 단계 4

나누고 보기와 맞추기

이제 깔끔한 합을 $8$로 나눈다.
$8\times 502 = 4016$이고 $4020-4016 = 4$이므로 $4020 = 8\times 502 + 4$이다.
나머지는 $4$이다.
따라서 원래의 거대한 합도 $8$로 나누면 나머지가 $4$이다.
보기 $0,1,2,4,6$ 중에서 이것은 $\textbf{(D)}\ 4$이다.

$$4020 \div 8 = 502 \text{ 나머지 } 4 \;\Rightarrow\; \textbf{(D)}\ 4$$

💡 작은 대체 합의 나머지가 곧 실제 합의 나머지이므로, 짧은 나눗셈 한 번으로 끝난다.

[1] #5 4.OA.C.5 $3$의 거듭제곱을 $8$로 나눈 나머지를 나열한다. $3^0=1$은 나머지 $1$, $3^1=3$은 나머지 $3$, $3^2=9=8+1$은 나

[2] #9 3.OA.B.5 합을 $8$로 나눈 나머지는 각 조각의 나머지로 정해진다. 작은 나머지들을 더한 뒤 그 합의 나머지를 구하면 된다. 그래서 실제 합 대신, 각

[3] #7 4.NBT.B.5 나머지를 둘씩 묶는다. $(1+3)$, 또 $(1+3)$, 이런 식이다. 각 짝의 합은 $4$이다. 항이 $2010$개이므로 $2010\div

[4] #3 4.NBT.B.6 이제 깔끔한 합을 $8$로 나눈다. $8\times 502 = 4016$이고 $4020-4016 = 4$이므로 $4020 = 8\times 50

검토

합리성 확인: 나머지 $4$는 $8$로 나눈 나머지가 반드시 그래야 하듯 $0$과 $7$ 사이에 있고, 보기와도 일치한다. 짧은 경우로 점검하면 $3^0+3^1+3^2+3^3 = 1+3+9+27 = 40 = 8\times 5$로 나머지 $0$인데, 짝짓기(각 $4$짜리 짝 두 개면 $8$, 나머지 $0$)와 맞는다. 여기에 $3^4+3^5$를 더하면 나머지 $1+3=4$가 더해지는데, 이는 마지막에 $4$짜리 짝 하나가 남는 $2010$개 항 계산과 일치한다.

대안 접근: 둘 대신 넷씩 묶어도 된다. 연속한 네 거듭제곱의 합은 $3^k(1+3+9+27)=3^k\cdot 40$이고 $40$은 $8$의 배수이므로, 네 개짜리 묶음마다 나머지가 $0$이다. $2010$개 항은 완전한 묶음 $502$개($2008$개 항)와 남는 $3^{2008}+3^{2009}$로 나뉘고, 이 둘의 나머지는 $1+3=4$이다. 따라서 답은 다시 $\textbf{(D)}\ 4$이다.

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

4.OA.C.5 주어진 규칙에 따라 수 또는 도형의 패턴 만들기 ($3$의 거듭제곱을 $8$로 나눈 나머지의 반복 주기 $1,3,1,3,\ldots$을 세우는 데 사용.)
3.OA.B.5 곱셈과 나눗셈 전략으로 연산의 성질 적용하기 (나머지를 더하고 다시 묶어도 되며, 그래서 합과 나머지의 합이 같은 나머지를 남긴다는 것을 정당화하는 데 사용.)
4.NBT.B.5 네 자리 이하 수와 한 자리 수의 곱셈 (값이 $4$인 짝 $1005$개를 곱 $1005\times 4 = 4020$으로 바꾸는 데 사용.)
4.NBT.B.6 네 자리 이하 피제수의 몫과 나머지 구하기 ($4020$을 $8$로 나눠 나머지 $4$를 읽어내는 데 사용.)

⭐ $3$의 거듭제곱은 $8$로 나누면 나머지가 $1,3,1,3$으로 반복된다. 둘씩 짝지으면 $4$짜리 짝이 $1005$개, 그 나머지는 $4$ — 보기 $\textbf{(D)}$이다.