AMC 10 · 2022 · #19

학년 7 number-theory

modular-arithmeticlcmfraction-arithmetic identify-subproblemscomplementary-counting ↑ 선수 지식: modular-arithmetic

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

문제

Define $L_n$ as the least common multiple of all the integers from $1$ to $n$ inclusive. There is a unique integer $h$ such that
$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{17}=\frac{h}{L_{17}}$
What is the remainder when $h$ is divided by $17$ ?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $L_n = \operatorname{lcm}(1, 2, \dots, n)$ 라 합시다. $\tfrac{1}{1} + \tfrac{1}{2} + \dots + \tfrac{1}{17} = \tfrac{h}{L_{17}}$ 를 만족하는 유일한 정수 $h$ 는 거대한 수입니다. $h$ 를 $17$ 로 나눈 나머지를 구하세요.

주어진 것: $L_{17} = \operatorname{lcm}(1, 2, \dots, 17)$; $\dfrac{1}{1} + \dfrac{1}{2} + \dots + \dfrac{1}{17} = \dfrac{h}{L_{17}}$; 선택지: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$

구하는 것: $h \bmod 17$

이해

주어진 것: $L_{17} = \operatorname{lcm}(1, 2, \dots, 17)$; $\dfrac{1}{1} + \dfrac{1}{2} + \dots + \dfrac{1}{17} = \dfrac{h}{L_{17}}$; 선택지: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$

계획

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

보조 도구: #16 관점 바꾸기, #13 대수로 바꾸기

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

실행 — 정답: C

#13 대수로 바꾸기 6.NS.A.1 단계 1

분모를 없앱니다.
양변에 $L_{17}$ 을 곱하면 정수들의 깔끔한 합이 나옴.

$$h = L_{17} \sum_{k=1}^{17} \dfrac{1}{k} = \sum_{k=1}^{17} \dfrac{L_{17}}{k}$$

💡 $L_{17}/k$ 가 정수인 이유: $L_{17}$ 은 $k \le 17$ 인 모든 $k$ 로 나누어지도록 만들어졌으니까.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 2

쪼개기 A: $k = 1, 2, \dots, 16$ 에 대해 $L_{17}/k$ 가 $17$ 의 배수임을 보이기.
$17$ 은 소수이고 $1 \le k \le 16$ 이므로 $\gcd(17, k) = 1$.
$L_{17} = 17 \cdot L_{16}$ (왜냐하면 $\gcd(L_{16}, 17) = 1$ 일 때 $\operatorname{lcm}(L_{16}, 17) = 17 \cdot L_{16}$).
그러면 $L_{17}/k = 17 \cdot (L_{16}/k)$ 이고 $k \mid L_{16}$ ($k \le 16$ 이므로) 이므로 $L_{16}/k$ 가 정수.
따라서 $L_{17}/k$ 는 $17 \cdot \text{정수}$.

$k \in \{1, \dots, 16\}$ 일 때 $\dfrac{L_{17}}{k} = 17 \cdot \dfrac{L_{16}}{k} \equiv 0 \pmod{17}$

💡 $L_{17}$ 안의 $17$ 인수는 $17$ 과 서로소인 무엇으로 나눠도 그대로 남습니다.

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

쪼개기 B: 살아남는 항은 $k = 17$ 뿐, $L_{17}/17 = L_{16}$.
따라서 $\bmod 17$ 에서 $h \equiv L_{16}$.

$$h \equiv \dfrac{L_{17}}{17} = L_{16} \pmod{17}$$

💡 $16$ 개 항은 $\bmod 17$ 에서 사라지고 하나만 남으며, 그 하나가 $L_{16}$.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 4

$L_{16}$ 을 소수 거듭제곱 인수분해: $16$ 이하 각 소수의 가장 큰 거듭제곱.
$16$ 이하 소수는 $2, 3, 5, 7, 11, 13$.
최고 거듭제곱: $2^4 = 16$, $3^2 = 9$, $5, 7, 11, 13$.

$$L_{16} = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 16 \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13$$

💡 $1, \dots, 16$ 의 LCM 은 $\le 16$ 인 각 소수의 가장 강한 인수를 모은 것.

#13 대수로 바꾸기 7.NS.A.2 단계 5

$L_{16} \bmod 17$ 계산.
$16 \equiv -1 \pmod{17}$ 로 바꾸고 한 단계씩 곱하면서 매번 $\bmod 17$ 로 줄임.

$$L_{16} \equiv (-1) \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \pmod{17}$$

💡 $16 \equiv -1$ 트릭으로 수도 부호도 작게 유지.

#13 대수로 바꾸기 7.NS.A.2 단계 6

단계별 축약 수행.
$(-1) \cdot 9 = -9 \equiv 8$.
$8 \cdot 5 = 40 \equiv 40 - 34 = 6$.
$6 \cdot 7 = 42 \equiv 42 - 34 = 8$.
$8 \cdot 11 = 88 \equiv 88 - 85 = 3$.
$3 \cdot 13 = 39 \equiv 39 - 34 = 5$.

$L_{16} \equiv 5 \pmod{17}$, 따라서 $h \equiv 5 \pmod{17} \;\Rightarrow\; \textbf{(C)}$

💡 곱할 때마다 축약 — 모든 중간값을 두 자리 안에 유지.

[1] #13 6.NS.A.1 분모를 없앱니다. 양변에 $L_{17}$ 을 곱하면 정수들의 깔끔한 합이 나옴.

[2] #7 6.NS.B.4 쪼개기 A: $k = 1, 2, \dots, 16$ 에 대해 $L_{17}/k$ 가 $17$ 의 배수임을 보이기. $17$ 은 소수이고 $1 \

[3] #16 6.NS.B.4 쪼개기 B: 살아남는 항은 $k = 17$ 뿐, $L_{17}/17 = L_{16}$. 따라서 $\bmod 17$ 에서 $h \equiv L_{

[4] #7 6.NS.B.4 $L_{16}$ 을 소수 거듭제곱 인수분해: $16$ 이하 각 소수의 가장 큰 거듭제곱. $16$ 이하 소수는 $2, 3, 5, 7, 11, 1

[5] #13 7.NS.A.2 $L_{16} \bmod 17$ 계산. $16 \equiv -1 \pmod{17}$ 로 바꾸고 한 단계씩 곱하면서 매번 $\bmod 17$ 로

[6] #13 7.NS.A.2 단계별 축약 수행. $(-1) \cdot 9 = -9 \equiv 8$. $8 \cdot 5 = 40 \equiv 40 - 34 = 6$. $6

검토

합리성 확인: 다른 순서로 독립 재확인: $9 \cdot 5 = 45 \equiv 45 - 34 = 11$; $7 \cdot 11 = 77 \equiv 77 - 68 = 9$; $11 \cdot 9 = 99 \equiv 99 - 85 = 14$; $13$ 곱하면 $14 \cdot 13 = 182 \equiv 182 - 170 = 12$; $-1$ ($16$ 에서) 곱하면 $12 \cdot (-1) = -12 \equiv 5 \pmod{17}$. 같은 답 $5$, 선택지 (C). $k \le 16$ 일 때 $L_{17}/k \equiv 0 \pmod{17}$ 라는 논증도 견고: $L_{17} = 17 \cdot L_{16}$ 이고 $k \mid L_{16}$ 이므로 $L_{17}/k = 17 (L_{16}/k)$ 는 $17$ 의 정수배.

대안 접근: 도구 #5 (패턴 찾기) — Wolstenholme 형 대칭: $k = 1, \dots, 8$ 에 대해 $\tfrac{1}{k} + \tfrac{1}{17-k}$ 짝짓기. 각 쌍의 합은 $\tfrac{17}{k(17-k)}$. $L_{17}$ 을 곱하면 $\tfrac{17 \cdot L_{17}}{k(17-k)}$ 즉 $17 \cdot (\text{정수})$ — $16$ 개 쌍이 모두 $\bmod 17$ 에서 사라지고 $L_{17}/17 = L_{16}$ 만 남음. 같은 결론, 나누어떨어짐 검사 적게.

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

6.NS.A.1 분수 나눗셈의 해석·계산 및 문장제 풀이 (조화 합의 분모 없애기: 양변에 $L_{17}$ 을 곱해 $h = \sum L_{17}/k$ 로 만드는 단계.)
6.NS.B.4 두 수의 최대공약수·최소공배수 ($L_{17} = \operatorname{lcm}(1, \dots, 17) = 17 \cdot L_{16}$ 다루기와 $L_{16}$ 의 소수 거듭제곱 성분 읽어내기.)
7.NS.A.2 유리수의 곱셈·나눗셈 이해 확장 ($L_{16} \bmod 17 = (-1) \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \bmod 17$ 을 매 단계 축약하며 계산.)

⭐ 양변에 $L_{17}$ 을 곱하면 $h$ 는 정수 $L_{17}/k$ 들의 $17$ 항 합. $17$ 이 소수이므로 $k = 1, \dots, 16$ 모두에서 $L_{17}/k$ 는 $17$ 의 배수 — 이 $16$ 항은 $\bmod 17$ 에서 사라집니다. 남는 것은 $L_{17}/17 = L_{16} = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ 뿐; 단계별로 $\bmod 17$ 축약하면 $\textbf{(C) }5$.