AMC 10 · 2024 · #18

학년 8 arithmetic

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

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

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

문제

정수 n이 모든 정수 위를 움직일 때, n¹⁰⁰을 125로 나눈 나머지는 서로 다른 값을 몇 개나 가질 수 있는가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

125

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

풀이 과정

전략 관점 바꾸기

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

1STEP 1

125 = 5³ 이니 소수는 5 하나뿐 — 모든 정수 n은 125와 서로소이거나 5의 배수, 둘 중 하나.

정수 전체 = {n : 5 ∤ n} n : 5 ∣ n

2STEP 2

경우 A — 5 ∤ n: φ(125) = 100 이고 지수도 100 이라, 오일러 정리로 n¹⁰⁰ ≡ 1 (mod 125).

φ(125) = 5³ - 5² = 100, n¹⁰⁰ ≡ 1 (mod 125)

3STEP 3

n = 2 확인: 2¹⁰ ≡ 24, 24⁵ ≡ -1 이니 2¹⁰⁰ ≡ (-1)² = 1 (mod 125) — 경우 A 확정.

2¹⁰ ≡ 24, 24⁵ ≡ -1, 2¹⁰⁰ ≡ (-1)² = 1 (mod 125)

4STEP 4

경우 B — 5 ∣ n: n = 5m 이면 n¹⁰⁰ = 5¹⁰⁰ m¹⁰⁰ 은 5³ = 125 의 배수라 나머지는 0.

n¹⁰⁰ = 5¹⁰⁰ m¹⁰⁰ = 125 · 5⁹⁷ m¹⁰⁰ ≡ 0 (mod 125)

5STEP 5

모든 정수 n은 두 경우 중 하나뿐, 가능한 나머지는 {0, 1} — 서로 다른 2개 → (B).

{n¹⁰⁰ mod 125 : n ∈ Z} = {0, 1}, |{0,1}| = 2 → (B)

정답

두 나머지 모두 실제로 나옴: n = 5 이면 5¹⁰⁰ 이 125 의 배수이므로 나머지 0, n = 1 이면 1¹⁰⁰ = 1 이므로 나머지 1. 두 값 모두 {0, 1, …, 124} 안. 선택지가 1, 2, 5, 25, 125 인데 — {0, 1} 의 크기 2 가 (B) 와 정확히 일치. 다른 밑으로 경우 A 추가 확인: n = 3: 3⁵ = 243 ≡ -7 (mod 125), 3¹⁰ ≡ 49, 3²⁰ ≡ 49² = 2401 ≡ 26, 3⁵⁰ ≡ 26² · 49 ≡ 51 · 49 = 2499 ≡ -1, 3¹⁰⁰ ≡ 1 (mod 125). 결론 일치.

💡핵심 정리

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

비슷한 유형 더 풀어보기