AMC 10 · 2022 · #19

학년 7 number-theory
modular-arithmeticlcmfraction-arithmetic identify-subproblemscomplementary-counting ↑ 선수 지식: modular-arithmetic
📏 중간 풀이 💡 3 개 인사이트
문제
L_n = lcm(1, 2, …, n) 라 합시다. 11\frac{1}{1} + 12\frac{1}{2} + … + 117\frac{1}{17} = hL17\frac{h}{L₁7} 를 만족하는 유일한 정수 h 는 거대한 수입니다. h 를 17 로 나눈 나머지를 구하세요.

답을 골라 클릭하세요.

(A)
1
(B)
3
(C)
5
(D)
7
(E)
9

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

풀이 과정
전략 작은 문제로 쪼개기

양변에 L₁7 을 곱하면 h = Σ_k=1¹⁷ L17k\frac{L₁7}{k} — 17 개 정수의 합이 됩니다. 도구 #7 (쪼개기) 가 두 부분으로 나눔: (a) 17 개 중 16 개는 17 로 나누어지므로 mod 17 에서 0, (b) 살아남는 한 항 L1717\frac{L₁7}{17} = L₁6 을 mod 17 로 계산. 도구 #16 (관점 바꾸기): h 를 직접 공격하지 말고 mod 17 에서 살아남는 것만 세기 — 거의 모든 게 사라집니다. 도구 #13 (대수로 바꾸기): L17k\frac{L₁7}{k} 를 기호적으로 다루며 gcd(17, k) = 1 로 나누어떨어짐 논증.

1STEP 1

분모를 없앱니다. 양변에 L₁7 을 곱하면 정수들의 깔끔한 합이 나옴.

h = L₁7 Σ_k=1¹⁷ 1k\frac{1}{k} = Σ_k=1¹⁷ L17k\frac{L₁7}{k}
2STEP 2

쪼개기 A: k = 1…16 에서 L₁7 = 17 · L₁6 이므로 각 L17k\frac{L₁7}{k} 는 17 의 배수.

k ∈ {1, …, 16} 일 때 L17k\frac{L₁7}{k} = 17 · L16k\frac{L₁6}{k} ≡ 0 (mod 17)
3STEP 3

쪼개기 B: 살아남는 항은 k = 17 뿐, L1717\frac{L₁7}{17} = L₁6, 따라서 h ≡ L₁6 (mod 17).

h ≡ L1717\frac{L₁7}{17} = L₁6 (mod 17)
4STEP 4

L₁6 을 소수 거듭제곱으로: 16 이하 각 소수의 최고 거듭제곱 → 2⁴ · 3² · 5 · 7 · 11 · 13.

L₁6 = 2⁴ · 3² · 5 · 7 · 11 · 13 = 16 · 9 · 5 · 7 · 11 · 13
5STEP 5

L₁6 mod 17 계산: 16 ≡ -1 (mod 17) 로 바꾸고 한 단계씩 곱하면서 매번 mod 17 로 줄임.

L₁6 ≡ (-1) · 9 · 5 · 7 · 11 · 13 (mod 17)
6STEP 6

곱할 때마다 축약: (-1)·9≡8, ·5≡6, ·7≡8, ·11≡3, ·13≡5, 따라서 h ≡ 5 (mod 17) → (C).

L₁6 ≡ 5 (mod 17), 따라서 h ≡ 5 (mod 17) → (C)
정답
5
다른 순서로 독립 재확인: 9 · 5 = 45 ≡ 45 - 34 = 11; 7 · 11 = 77 ≡ 77 - 68 = 9; 11 · 9 = 99 ≡ 99 - 85 = 14; 13 곱하면 14 · 13 = 182 ≡ 182 - 170 = 12; -1 (16 에서) 곱하면 12 · (-1) = -12 ≡ 5 (mod 17). 같은 답 5, 선택지 (C). k ≤ 16 일 때 L17k\frac{L₁7}{k} ≡ 0 (mod 17) 라는 논증도 견고: L₁7 = 17 · L₁6 이고 k ∣ L₁6 이므로 L17k\frac{L₁7}{k} = 17 (L16k\frac{L₁6}{k}) 는 17 의 정수배.
💡핵심 정리

양변에 L₁7 을 곱하면 h 는 정수 L17k\frac{L₁7}{k} 들의 17 항 합. 17 이 소수이므로 k = 1, …, 16 모두에서 L17k\frac{L₁7}{k} 는 17 의 배수 — 이 16 항은 mod 17 에서 사라집니다. 남는 것은 L1717\frac{L₁7}{17} = L₁6 = 2⁴ · 3² · 5 · 7 · 11 · 13 뿐; 단계별로 mod 17 축약하면 (C) 5.