AMC 10 · 2020 · #24
학년 6 number-theory문제
Let n be the least positive integer greater than 1000 for which
gcd(63,n+120)=21andgcd(n+63,120)=60.
What is the sum of the digits of n?
답을 골라 클릭하세요.
AMC 10 2020 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + 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$ 을 찾고, 그 자릿수의 합을 구하세요.
주어진 것: $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$
계획
주요 도구: #7 작은 문제로 쪼개기
보조 도구: #5 패턴 찾기, #6 추측하고 확인하기, #3 가능성 지우기
도구 #7(작은 문제로 쪼개기): 각 GCD 조건을 "나눠진다" 와 "안 나눠진다" 두 조각으로 분해. 도구 #5(패턴): 두 조건이 각각 등차수열을 주고, 그 교집합 패턴을 찾기. 도구 #6(추측·확인): 결국 $n = 420j + 237$ ($j = 2, 3, 4, \ldots$) 후보를 차례로 확인. 도구 #3(가능성 지우기): $j=2, 3$ 은 비분할 조건에서 탈락, $j=4$ 가 통과.
실행 — 정답: C
6.NS.B.4 단계 1 - 조건 1 분해.
- $\gcd(63, n+120) = 21$ 은 두 가지를 동시 요구: (i) $21$ 이 $n+120$ 을 나눔; (ii) $63$ 이 안 나눔, 즉 $9 \nmid (n+120)$ (만약 $9$ 가 나누면 $\gcd$ 가 $63$ 이 됨).
- 첫 번째는 나눠짐, 두 번째는 최종 필터.
💡 $\gcd = 21$ 은 "$21$ 로 나눠짐" + "$63$ 으로는 안 나눠짐" 의 두 메시지.
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$ 의 두 번째 인수뿐.
💡 $\gcd = 60$ vs. $120$ 의 차이는 $2$ 한 인수 — 추적 쉬움.
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$).
💡 나눠짐 조건을 깔끔한 두 합동식으로.
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$.
💡 두 합동식을 대입하면 주기 $420 = \mathrm{lcm}(21, 60)$ 이 자연히 나옴.
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$.
- 두 비분할 필터를 순서대로 적용.
💡 작은 후보부터 나열하고 부가 조건 검사.
6.NS.B.2 단계 6 - $j=2 \Rightarrow n=1077$.
- $n + 120 = 1197 = 9 \cdot 133$ 이라 $9 \mid 1197$ — 조건 (i) 위반 ($\gcd = 63$).
- 탈락.
💡 자릿수 합 $1+1+9+7 = 18$ 이 $9$ 의 배수 — 빠른 자릿수 검사로 탈락.
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$).
- 탈락.
💡 $60$ 으로 나눈 몫이 짝수 — $120$ 도 나누므로 $\gcd$ 가 한 단계 더 큼.
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 조건 모두 만족.
💡 부가 조건 모두 통과하는 첫 후보 — 최솟값 확정.
4.OA.A.3 단계 9 $1917$ 의 자릿수 합: $1 + 9 + 1 + 7 = 18$, 선택지 (C).
💡 네 자릿수를 더하면 끝.
6.NS.B.4 조건 1 분해. $\gcd(63, n+120) = 21$ 은 두 가지를 동시 요구: (i) $21$ 이 $n+120$ 을 나눔; (ii) $63 6.NS.B.4 조건 2 분해. $\gcd(n+63, 120) = 60$ 은: (i) $60 \mid (n+63)$; (ii) $120 \nmid (n+63)$ 6.EE.B.7 합동식으로 변환. $n + 120 \equiv 0 \pmod{21}$ 은 $n \equiv -120 \equiv 6 \pmod{21}$ ($-1 6.EE.B.7 두 합동식 결합. 두 번째에서 $n = 60k + 57$. 첫 번째에 대입: $60k + 57 \equiv 6 \pmod{21}$. $60 \e 4.OA.A.3 $> 1000$ 후보. $420 j + 237 > 1000$ 에서 $j > 763/420 \approx 1.81$. 후보 목록: $n = 107 6.NS.B.2 $j=2 \Rightarrow n=1077$. $n + 120 = 1197 = 9 \cdot 133$ 이라 $9 \mid 1197$ — 조건 ( 6.NS.B.2 $j=3 \Rightarrow n=1497$. $n+120 = 1617$, 자릿수 합 $1+6+1+7 = 15$ — $9$ 의 배수 아님, 통과 6.NS.B.2 $j=4 \Rightarrow n=1917$. $n+120 = 2037$, 자릿수 합 $2+0+3+7 = 12$ — $9$ 의 배수 아님, 통과 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$.
⭐ 이 AMC 10 문제는 이미 배운 6학년 최대공약수와 나눠짐만 있으면 풀려요 — 각 $\gcd$ 조건이 "딱 나눠짐 + 더는 안 나눠짐" 으로 쪼개져 후보 $1077, 1497, 1917, \ldots$ ($420$ 간격) 가 나오고, 앞 두 개가 한 쪽 부가 조건에서 탈락해 $n = 1917$ 의 자릿수 합 $1+9+1+7=18$.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.