AMC 10 · 2020 · #24

학년 6 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Logic-Deduction / Elimination

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

📏 긴 풀이 💡 3 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 작은 문제로 쪼개기

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

1STEP 1

조건 1 분해: 21 ∣ (n+120) 이지만 9 ∤ (n+120) — 아니면 gcd 가 63 이 됨.

21 ∣ (n+120) 이고 9 ∤ (n+120)

2STEP 2

조건 2 분해: 60 ∣ (n+63) 이지만 $\frac{n+63}{60}$ 은 홀수 — 120 까지 남은 건 2 한 인수뿐.

60 ∣ (n+63) 이고

\frac{n+63}{60}

홀수

3STEP 3

합동식으로 변환: n+120 ≡ 0 (mod 21) 은 n ≡ 6 (mod 21), 60 ∣ (n+63) 은 n ≡ 57 (mod 60).

n ≡ 6 (mod 21), n ≡ 57 (mod 60)

4STEP 4

n = 60k + 57 을 첫 식에 대입해 풀면 k ≡ 3 (mod 7), 즉 n = 420j + 237 (주기 = lcm(21,60)).

n = 420 j + 237 (정수 j ≥ 0)

5STEP 5

420j + 237 ＞ 1000 이려면 j ≥ 2; 후보는 n = 1077, 1497, 1917, … 순으로 필터 적용.

j=2 → 1077; j=3 → 1497; j=4 → 1917

6STEP 6

n = 1077 검사: n+120 = 1197 = 9 · 133 이라 9 ∣ 1197 — 조건 (i) 위반 (gcd = 63). 탈락.

\frac{1197}{9}

= 133 → 9 ∣ 1197 (불통)

7STEP 7

n = 1497 검사: 9 ∤ 1617 통과하지만 n+63 = 1560, $\frac{1560}{60}$ = 26 짝수 — 조건 (ii) 위반. 탈락.

\frac{n+63}{60}

\frac{1560}{60}

= 26 (짝수, 불통)

8STEP 8

n = 1917 검사: 9 ∤ 2037 통과, n+63 = 1980, $\frac{1980}{60}$ = 33 홀수 — n = 1917 이 두 조건 통과.

n=1917;

\frac{2037}{21}

= 97, 9 ∤ 2037;

\frac{1980}{60}

= 33 홀수

9STEP 9

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

1 + 9 + 1 + 7 = 18 → (C)

정답

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

💡핵심 정리

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

비슷한 유형 더 풀어보기