AMC 10 · 2017 · #23

학년 6 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

modular-arithmeticdivisibility-rulesdigit-sum chinese-remainder-theoremidentify-subproblems ↑ 선수 지식: modular-arithmetic

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

문제

1, 2, 3, ... , 44를 차례로 이어 붙여 만든 79자리 수 N = 123456789101112...4344가 있다. N을 45로 나눈 나머지를 구하라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 작은 문제로 쪼개기

79자리 수를 45로 직접 나누는 것은 불가능하다. 하지만 45 = 9 x 5이고 9와 5는 공약수가 없으므로, 45로 나눈 나머지는 9로 나눈 나머지와 5로 나눈 나머지가 정해지면 함께 정해진다. 둘 다 쉽다. 5로 나눈 나머지는 끝자리만으로, 9로 나눈 나머지는 각 자리 숫자의 합만으로 정해진다. 두 작은 나머지를 구한 뒤, 둘 다 만족하는 몇 안 되는 경우를 확인하면 된다.

1STEP 1

45를 9와 5로 쪼개기

45 = 9 × 5로 쪼갠다. 9와 5는 서로소라 N mod 45는 N mod 9와 N mod 5로 정해진다. 쉬운 나눗셈 둘로 바뀐다.

45 = 9 × 5, gcd(9,5)=1

2STEP 2

5로 나눈 나머지

5로 나눈 나머지는 끝자리만으로 정해진다. N의 끝자리는 4이므로 N을 5로 나눈 나머지는 4이다.

N = 10q + 4 ≡ 4 (mod 5)

3STEP 3

9로 나눈 나머지

9로 나눈 나머지는 자리 숫자 합의 나머지와 같다. 1+2+…+44 = 990 = 9 × 110이므로 N mod 9 = 0이다.

1+2+…+44 = (44 · 45)/2 = 990 = 9 × 110 ≡ 0 (mod 9)

4STEP 4

두 단서 합치기

9의 배수이면서 5로 나눈 나머지가 4인 수를 찾자. 0, 9, 18, 27, 36 중 9만 맞다(9 = 5 + 4). 답은 (C)이다.

x ≡ 0 (mod 9), x ≡ 4 (mod 5) → x ∈ {0,9,18,27,36}, x=9

정답

나머지 9는 45보다 작아야 하는데 실제로 그렇다. 두 조각으로 빠르게 점검하면, 9를 5로 나누면 나머지가 4이고(5로 나눈 단서와 일치), 9는 9의 배수이다(9로 나눈 단서와 일치). 두 조건이 모두 성립하므로 9는 모순이 없다.

💡핵심 정리

거대한 수를 45로 나눌 때는 45를 9와 5로 쪼개라. 끝자리가 5를 맡고 자리 숫자 합이 9를 맡으니, 둘 다 맞는 나머지 하나를 찾으면 된다.

45를 9와 5로 쪼개기
5로 나눈 나머지
9로 나눈 나머지
두 단서 합치기

45를 9와 5로 쪼개기

5로 나눈 나머지

9로 나눈 나머지

두 단서 합치기

비슷한 유형 더 풀어보기