AMC 10 · 2024 · #18

학년 8 arithmetic

modular-arithmeticexponentseulers-theoremprime-factorization complementary-countingidentify-subproblemscasework ↑ 선수 지식: modular-arithmeticexponentsprime-factorization

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

문제

How many different remainders can result when the $100$ th power of an integer is
divided by $125$ ?

$\textbf{(A) } 1 \qquad\textbf{(B) } 2 \qquad\textbf{(C) } 5 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 125$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

125

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 정수 $n$이 모든 정수 위를 움직일 때, $n^{100}$을 $125$로 나눈 나머지는 서로 다른 값을 몇 개나 가질 수 있는가?

주어진 것: $n$ 은 정수 (양수·음수·$0$); 나누는 수 $= 125 = 5^3$; 지수 $= 100$; $\phi(125) = 5^3 - 5^2 = 100$ (오일러 토션트 — 서로소 경우에 쓰이는 알려진 사실); 선택지: (A) $1$, (B) $2$, (C) $5$, (D) $25$, (E) $125$

구하는 것: $n$ 이 정수 전체를 움직일 때 $n^{100} \pmod{125}$ 의 서로 다른 값의 개수

이해

문제 재정리: 정수 $n$이 모든 정수 위를 움직일 때, $n^{100}$을 $125$로 나눈 나머지는 서로 다른 값을 몇 개나 가질 수 있는가?

계획

주요 도구: #16 관점 바꾸기

보조 도구: #7 작은 문제로 쪼개기, #9 더 쉬운 문제로 줄이기

모든 정수는 $125$의 소인수 $5$를 공유하거나 그렇지 않거나 둘 중 하나 — 도구 #16(관점 바꾸기)으로 이 이분법을 잡으면 어려운 한 문제가 쉬운 두 문제로 변합니다. 도구 #7(작은 문제로 쪼개기)이 두 경우를 처리합니다: (a) $n$이 $125$와 서로소 — 오일러 정리가 $\phi(125) = 100$ 임을 이용해 $n^{100} \equiv 1 \pmod{125}$ 을 한 줄로 끝냄, (b) $n$이 $5$의 배수 — $n^{100} = 5^{100} k^{100}$ 은 $5^{100} \gg 5^3 = 125$ 의 배수라 나머지 $0$. 도구 #9(더 쉬운 문제로 줄이기)는 $n = 2$ 같은 작은 경우에서 (a)의 결론을 검증해, 정리 이름만 믿지 않고 답을 단단히 합니다.

실행 — 정답: B

#16 관점 바꾸기 6.NS.B.4 단계 1

중요한 단 하나의 소수로 분기.
나누는 수 $125 = 5^3$ 이므로 신경 쓸 소수는 $5$ 하나뿐.
임의의 정수 $n$은 정확히 두 통 — $\gcd(n, 125) = 1$ ($5$ 의 배수가 아님) 과 $5 \mid n$ — 중 하나에 들어갑니다.

$$\text{정수 전체} = \{n : 5 \nmid n\} \sqcup \{n : 5 \mid n\}$$

💡 $125$의 소인수만 본다 — 6학년 최대공약수·최소공배수 관점에서 분기를 잡는 무브.

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

경우 A: $5 \nmid n$, 즉 $n$이 $125$와 서로소.
오일러 정리로 $n^{\phi(125)} \equiv 1 \pmod{125}$, 그리고 $\phi(125) = 5^3 - 5^2 = 125 - 25 = 100$.
문제의 지수가 정확히 $100$ 이므로 모든 그런 $n$에 대해 $n^{100} \equiv 1 \pmod{125}$.

$$\phi(125) = 5^3 - 5^2 = 100, \quad n^{100} \equiv 1 \pmod{125}$$

💡 지수가 토션트 $\phi$ 와 일치하면 서로소 밑은 모두 $1$ 로 떨어진다 — 8학년 정수 지수 성질의 깔끔한 한 줄.

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

작은 값으로 경우 A 검증.
$n = 2$ ($125$와 서로소): $2^{10} = 1024 = 8 \cdot 125 + 24$ 이므로 $2^{10} \equiv 24 \pmod{125}$.
그러면 $2^{100} = (2^{10})^{10} \equiv 24^{10} \pmod{125}$.
차례로 제곱: $24^2 = 576 \equiv 76$, $24^4 \equiv 76^2 = 5776 \equiv 26$, $24^5 \equiv 24 \cdot 26 = 624 \equiv 124 \equiv -1$, 따라서 $24^{10} \equiv (-1)^2 = 1 \pmod{125}$.
확정: $2^{100} \equiv 1 \pmod{125}$.

$$2^{10} \equiv 24, \; 24^5 \equiv -1, \; 2^{100} \equiv (-1)^2 = 1 \pmod{125}$$

💡 $n = 2$ 의 작은 검증으로 정리 이름에만 기대지 않고 결론을 확인.

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

경우 B: $5 \mid n$.
$n = 5m$ ($m$ 정수) 으로 쓰면 $n^{100} = (5m)^{100} = 5^{100} \cdot m^{100}$.
$5^{100}$ 은 $5^3 = 125$ 의 배수(사실 훨씬 더 높은 거듭제곱) 이므로 $n^{100}$ 은 $125$ 의 배수, 나머지는 $0$.

$$n^{100} = 5^{100} m^{100} = 125 \cdot 5^{97} m^{100} \equiv 0 \pmod{125}$$

💡 $5^{100}$ 안의 $5^3$ 한 덩이가 이미 나누는 수를 먹어 치워, 나머지는 끌려갈 뿐.

#16 관점 바꾸기 5.OA.A.2 단계 5

두 경우 결합.
모든 정수 $n$은 두 경우 중 정확히 하나에 들어가며, 등장하는 나머지는 $0$ (경우 B) 과 $1$ (경우 A) 뿐.
가능한 나머지의 집합은 $\{0, 1\}$ — $2$ 개.

$$\{n^{100} \bmod 125 : n \in \mathbb{Z}\} = \{0, \; 1\}, \quad |\{0,1\}| = 2 \;\Rightarrow\; \textbf{(B)}$$

💡 관점 바꾸기로 둘로 가르고 각 쪽이 정확히 하나의 나머지를 내놓음 — 5학년 "답을 작은 집합으로 쓰기".

[1] #16 6.NS.B.4 중요한 단 하나의 소수로 분기. 나누는 수 $125 = 5^3$ 이므로 신경 쓸 소수는 $5$ 하나뿐. 임의의 정수 $n$은 정확히 두 통 —

[2] #7 8.EE.A.1 경우 A: $5 \nmid n$, 즉 $n$이 $125$와 서로소. 오일러 정리로 $n^{\phi(125)} \equiv 1 \pmod{125}

[3] #9 8.EE.A.1 작은 값으로 경우 A 검증. $n = 2$ ($125$와 서로소): $2^{10} = 1024 = 8 \cdot 125 + 24$ 이므로 $2^

[4] #7 8.EE.A.1 경우 B: $5 \mid n$. $n = 5m$ ($m$ 정수) 으로 쓰면 $n^{100} = (5m)^{100} = 5^{100} \cdot

[5] #16 5.OA.A.2 두 경우 결합. 모든 정수 $n$은 두 경우 중 정확히 하나에 들어가며, 등장하는 나머지는 $0$ (경우 B) 과 $1$ (경우 A) 뿐. 가능

검토

합리성 확인: 두 나머지 모두 실제로 나옴: $n = 5$ 이면 $5^{100}$ 이 $125$ 의 배수이므로 나머지 $0$, $n = 1$ 이면 $1^{100} = 1$ 이므로 나머지 $1$. 두 값 모두 $\{0, 1, \dots, 124\}$ 안. 선택지가 $1, 2, 5, 25, 125$ 인데 — $\{0, 1\}$ 의 크기 $2$ 가 (B) 와 정확히 일치. 다른 밑으로 경우 A 추가 확인: $n = 3$: $3^5 = 243 \equiv -7 \pmod{125}$, $3^{10} \equiv 49$, $3^{20} \equiv 49^2 = 2401 \equiv 26$, $3^{50} \equiv 26^2 \cdot 49 \equiv 51 \cdot 49 = 2499 \equiv -1$, $3^{100} \equiv 1 \pmod{125}$. 결론 일치.

대안 접근: 도구 #5(패턴 찾기): $n = 0, 1, 2, \dots, 10$ 에 대해 $n^{100} \bmod 125$ 의 표를 만들면 값이 $0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0$. 패턴 "$5 \mid n$ 이면 $0$, 그 외에는 $1$" 이 오일러를 직접 부르지 않아도 곧장 드러납니다. 같은 답: 서로 다른 나머지 $2$ 개.

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

6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 ($125 = 5^3$ 의 유일한 소인수가 $5$ 임을 인식해 모든 정수 $n$ 을 서로소 경우와 $5$ 의 배수 경우로 가르는 데 사용.)
8.EE.A.1 정수 지수의 성질을 알고 적용하기 (서로소 경우에는 오일러 정리 $n^{\phi(125)} \equiv 1 \pmod{125}$, $5$ 의 배수 경우에는 $(5m)^{100} = 5^{100} m^{100}$ 을 활용.)
5.OA.A.2 수의 계산을 기록하는 식 쓰기 (답을 집합 $\{0, 1\}$ 로 기록하고 그 크기 $2$ 를 읽어내는 데 사용.)

⭐ 이 AMC 10 문제는 8학년의 정수 지수 성질과 "$n$ 이 $5$ 의 배수인가 아닌가" 라는 깔끔한 두 가름만으로 풀려요 — 가능한 나머지 집합이 단지 $\{0, 1\}$ 인 거죠!

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기