AMC 10 · 2020 · #24

학년 6 number-theory

gcddivisibility-ruleslcmmodular-arithmeticprime-factorizationdigit-sum caseworksystematic-enumerationidentify-subproblems ↑ 선수 지식: gcdprime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

Let $n$ be the least positive integer greater than $1000$ for which

$\gcd(63, n+120) =21\quad \text{and} \quad \gcd(n+63, 120)=60.$

What is the sum of the digits of $n$ ?

$\textbf{(A) } 12 \qquad\textbf{(B) } 15 \qquad\textbf{(C) } 18 \qquad\textbf{(D) } 21\qquad\textbf{(E) } 24$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $\gcd(63, n+120) = 21$ 과 $\gcd(n+63, 120) = 60$ 을 모두 만족하는 $1000$ 보다 큰 가장 작은 양의 정수 $n$ 을 찾고, 그 자릿수의 합을 구하세요.

주어진 것: $63 = 9 \cdot 7 = 3^2 \cdot 7$; $120 = 8 \cdot 15 = 2^3 \cdot 3 \cdot 5$; 조건 1: $\gcd(63, n+120) = 21$; 조건 2: $\gcd(n+63, 120) = 60$; $n > 1000$; 그런 $n$ 중 최솟값과 그 자릿수 합; 선택지: (A) $12$, (B) $15$, (C) $18$, (D) $21$, (E) $24$

구하는 것: $n > 1000$ 인 최소의 유효 $n$ 과 자릿수 합

이해

문제 재정리: $\gcd(63, n+120) = 21$ 과 $\gcd(n+63, 120) = 60$ 을 모두 만족하는 $1000$ 보다 큰 가장 작은 양의 정수 $n$ 을 찾고, 그 자릿수의 합을 구하세요.

계획

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

보조 도구: #5 패턴 찾기, #6 추측하고 확인하기, #3 가능성 지우기

도구 #7(작은 문제로 쪼개기): 각 GCD 조건을 "나눠진다" 와 "안 나눠진다" 두 조각으로 분해. 도구 #5(패턴): 두 조건이 각각 등차수열을 주고, 그 교집합 패턴을 찾기. 도구 #6(추측·확인): 결국 $n = 420j + 237$ ($j = 2, 3, 4, \ldots$) 후보를 차례로 확인. 도구 #3(가능성 지우기): $j=2, 3$ 은 비분할 조건에서 탈락, $j=4$ 가 통과.

실행 — 정답: C

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

조건 1 분해.
$\gcd(63, n+120) = 21$ 은 두 가지를 동시 요구: (i) $21$ 이 $n+120$ 을 나눔; (ii) $63$ 이 안 나눔, 즉 $9 \nmid (n+120)$ (만약 $9$ 가 나누면 $\gcd$ 가 $63$ 이 됨).
첫 번째는 나눠짐, 두 번째는 최종 필터.

$$21 \mid (n+120) \;\text{ 이고 }\; 9 \nmid (n+120)$$

💡 $\gcd = 21$ 은 "$21$ 로 나눠짐" + "$63$ 으로는 안 나눠짐" 의 두 메시지.

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

조건 2 분해.
$\gcd(n+63, 120) = 60$ 은: (i) $60 \mid (n+63)$; (ii) $120 \nmid (n+63)$, 즉 $(n+63)/60$ 이 홀수 ($120 = 2 \cdot 60$).
다른 소인수 $3, 5$ 는 이미 $60$ 에 포화돼 있어 추가 장애물은 $2$ 의 두 번째 인수뿐.

$$60 \mid (n+63) \;\text{ 이고 }\; (n+63)/60 \text{ 홀수}$$

💡 $\gcd = 60$ vs. $120$ 의 차이는 $2$ 한 인수 — 추적 쉬움.

#5 패턴 찾기 6.EE.B.7 단계 3

합동식으로 변환.
$n + 120 \equiv 0 \pmod{21}$ 은 $n \equiv -120 \equiv 6 \pmod{21}$ ($-120 + 126 = 6$).
$60 \mid (n+63)$ 은 $n \equiv -63 \equiv 57 \pmod{60}$ ($-63 + 120 = 57$).

$$n \equiv 6 \pmod{21}, \;\; n \equiv 57 \pmod{60}$$

💡 나눠짐 조건을 깔끔한 두 합동식으로.

#5 패턴 찾기 6.EE.B.7 단계 4

두 합동식 결합.
두 번째에서 $n = 60k + 57$.
첫 번째에 대입: $60k + 57 \equiv 6 \pmod{21}$.
$60 \equiv 18 \pmod{21}$, $57 \equiv 15 \pmod{21}$ 이라 $18k + 15 \equiv 6 \pmod{21}$, 즉 $18k \equiv -9 \equiv 12 \pmod{21}$.
$\gcd(18, 21) = 3$ 으로 나누기 (확인: $3 \mid 12$): $6k \equiv 4 \pmod 7$.
$6 \equiv -1 \pmod 7$ 이라 $-k \equiv 4$, $k \equiv -4 \equiv 3 \pmod 7$.
따라서 $k = 7j+3$, $n = 60(7j+3) + 57 = 420 j + 237$.

$$n = 420 j + 237 \;\text{ (정수 } j \ge 0)$$

💡 두 합동식을 대입하면 주기 $420 = \mathrm{lcm}(21, 60)$ 이 자연히 나옴.

#6 추측하고 확인하기 4.OA.A.3 단계 5

$> 1000$ 후보.
$420 j + 237 > 1000$ 에서 $j > 763/420 \approx 1.81$.
후보 목록: $n = 1077 (j=2), 1497 (j=3), 1917 (j=4), 2337 (j=5), \ldots$.
두 비분할 필터를 순서대로 적용.

$$j=2 \Rightarrow 1077; \;\; j=3 \Rightarrow 1497; \;\; j=4 \Rightarrow 1917$$

💡 작은 후보부터 나열하고 부가 조건 검사.

#3 가능성 지우기 6.NS.B.2 단계 6

$j=2 \Rightarrow n=1077$.
$n + 120 = 1197 = 9 \cdot 133$ 이라 $9 \mid 1197$ — 조건 (i) 위반 ($\gcd = 63$).
탈락.

$$1197 / 9 = 133 \Rightarrow 9 \mid 1197 \;\text{ (불통)}$$

💡 자릿수 합 $1+1+9+7 = 18$ 이 $9$ 의 배수 — 빠른 자릿수 검사로 탈락.

#3 가능성 지우기 6.NS.B.2 단계 7

$j=3 \Rightarrow n=1497$.
$n+120 = 1617$, 자릿수 합 $1+6+1+7 = 15$ — $9$ 의 배수 아님, 통과.
$n+63 = 1560$, $1560/60 = 26$ 짝수 — 조건 (ii) 위반 ($\gcd = 120$).
탈락.

$$(n+63)/60 = 1560/60 = 26 \;\text{ (짝수, 불통)}$$

💡 $60$ 으로 나눈 몫이 짝수 — $120$ 도 나누므로 $\gcd$ 가 한 단계 더 큼.

#6 추측하고 확인하기 6.NS.B.2 단계 8

$j=4 \Rightarrow n=1917$.
$n+120 = 2037$, 자릿수 합 $2+0+3+7 = 12$ — $9$ 의 배수 아님, 통과.
$n+63 = 1980$, $1980/60 = 33$ 홀수 — 통과.
$n=1917$ 이 두 GCD 조건 모두 만족.

$$n=1917; \;\; 2037/21 = 97, \;\; 9 \nmid 2037; \;\; 1980/60 = 33 \text{ 홀수}$$

💡 부가 조건 모두 통과하는 첫 후보 — 최솟값 확정.

#6 추측하고 확인하기 4.OA.A.3 단계 9

$1917$ 의 자릿수 합: $1 + 9 + 1 + 7 = 18$, 선택지 (C).

$$1 + 9 + 1 + 7 = 18 \Rightarrow \textbf{(C)}$$

💡 네 자릿수를 더하면 끝.

[1] #7 6.NS.B.4 조건 1 분해. $\gcd(63, n+120) = 21$ 은 두 가지를 동시 요구: (i) $21$ 이 $n+120$ 을 나눔; (ii) $63

[2] #7 6.NS.B.4 조건 2 분해. $\gcd(n+63, 120) = 60$ 은: (i) $60 \mid (n+63)$; (ii) $120 \nmid (n+63)$

[3] #5 6.EE.B.7 합동식으로 변환. $n + 120 \equiv 0 \pmod{21}$ 은 $n \equiv -120 \equiv 6 \pmod{21}$ ($-1

[4] #5 6.EE.B.7 두 합동식 결합. 두 번째에서 $n = 60k + 57$. 첫 번째에 대입: $60k + 57 \equiv 6 \pmod{21}$. $60 \e

[5] #6 4.OA.A.3 $> 1000$ 후보. $420 j + 237 > 1000$ 에서 $j > 763/420 \approx 1.81$. 후보 목록: $n = 107

[6] #3 6.NS.B.2 $j=2 \Rightarrow n=1077$. $n + 120 = 1197 = 9 \cdot 133$ 이라 $9 \mid 1197$ — 조건 (

[7] #3 6.NS.B.2 $j=3 \Rightarrow n=1497$. $n+120 = 1617$, 자릿수 합 $1+6+1+7 = 15$ — $9$ 의 배수 아님, 통과

[8] #6 6.NS.B.2 $j=4 \Rightarrow n=1917$. $n+120 = 2037$, 자릿수 합 $2+0+3+7 = 12$ — $9$ 의 배수 아님, 통과

[9] #6 4.OA.A.3 $1917$ 의 자릿수 합: $1 + 9 + 1 + 7 = 18$, 선택지 (C).

검토

합리성 확인: 직접 검증: $n=1917$ 에서 $\gcd(63, 2037) = \gcd(63, 2037 \bmod 63) = \gcd(63, 21) = 21$ ✓ ($2037 = 32 \cdot 63 + 21$). $\gcd(1980, 120) = \gcd(120, 1980 \bmod 120) = \gcd(120, 60) = 60$ ✓. 더 작은 후보 $1077, 1497$ 은 부가 조건에서 탈락했으므로 $1917$ 이 진짜 최솟값. 자릿수 합 $1+9+1+7 = 18$ 은 선택지 (C). 함정 (D) $21$ 은 "$\gcd = 21$" 을 그대로 답으로 옮기는 오류, (A) $12$ 는 $j=2,3$ 을 빠뜨리고 잘못된 $n$ 을 고른 경우.

대안 접근: 도구 #6(추측·확인) 만으로: $n=1001$ 부터 시작해 먼저 $n \equiv 57 \pmod{60}$ 이고 $(n+63)/60$ 이 홀수인 $n$ 후보들 $\{1077, 1197, 1317, \ldots\}$ (주기 $120$, 짝수·홀수 몫이 번갈음) 을 만들고, 각각이 $n + 120 \equiv 0 \pmod{21}$ 그리고 $9 \nmid (n+120)$ 인지 확인. 교차해 곧장 $1917$ 에 도달.

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

4.OA.A.3 네 가지 연산을 이용한 여러 단계 문장제 해결 (등차수열 $420 j + 237$ 구성과 $1917$ 의 자릿수 네 개 합산.)
6.NS.B.2 표준 나눗셈 알고리즘으로 여러 자릿수 나누기 ($2037/21, 1980/60, 1197/9$ 등의 몫을 계산해 비분할 조건 검증.)
6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 (각 $\gcd$ 조건을 "나눠짐 + 비분할" 두 조각으로 분해, $\mathrm{lcm}(21, 60) = 420$ 적용.)
6.EE.B.7 $px = q$ 형 일차방정식 풀이 (나눠짐 조건을 합동식으로 변환하고 $n \equiv 6 \pmod{21}$ 과 $n \equiv 57 \pmod{60}$ 을 결합해 $n = 420j + 237$ 도출.)

⭐ 이 AMC 10 문제는 이미 배운 6학년 최대공약수와 나눠짐만 있으면 풀려요 — 각 $\gcd$ 조건이 "딱 나눠짐 + 더는 안 나눠짐" 으로 쪼개져 후보 $1077, 1497, 1917, \ldots$ ($420$ 간격) 가 나오고, 앞 두 개가 한 쪽 부가 조건에서 탈락해 $n = 1917$ 의 자릿수 합 $1+9+1+7=18$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

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

비슷한 유형 더 풀어보기