AMC 10 · 2017 · #19
학년 6 number-theory modular-arithmeticdivisibility-rulesdigit-sum chinese-remainder-theoremidentify-subproblems ↑ 선수 지식: modular-arithmetic
📏 중간 풀이 💡 2 개 인사이트
문제
1부터 44까지의 수를 차례로 이어 붙여 79자리의 큰 수 N을 만듭니다. N을 45로 나눈 나머지를 구하세요.
답을 골라 클릭하세요.
(A)
1
(B)
4
(C)
9
(D)
18
(E)
44
풀이 과정
전략 작은 문제로 쪼개기
79자리 수를 45로 직접 나누는 것은 불가능하다. 하지만 45 = 9 x 5이고 9와 5는 공약수가 없으므로, 45로 나눈 나머지는 9로 나눈 나머지와 5로 나눈 나머지가 정해지면 함께 정해진다. 둘 다 쉽다. 5로 나눈 나머지는 끝자리만으로, 9로 나눈 나머지는 각 자리 숫자의 합만으로 정해진다. 두 작은 나머지를 구한 뒤, 둘 다 만족하는 몇 안 되는 경우를 확인하면 된다.
1STEP 1
45를 9와 5로 쪼개기
45를 서로소인 두 수로 쪼갭니다.
45 = 9 × 5, gcd(9,5)=1
45를 서로소인 9와 5로 쪼개면 불가능한 나눗셈 하나가 쉬운 나눗셈 둘로 바뀐다.
6.NS.B.4Identify Subproblems2STEP 2
5로 나눈 나머지
5 쪽은 끝자리만 보면 됩니다.
N = 10q + 4 ≡ 4 (mod 5)
십, 백, 그 이상의 자리는 모두 5의 배수라서 끝자리만 나머지를 남긴다.
4.NBT.B.6Look For A Pattern3STEP 3
9로 나눈 나머지
9 쪽은 자릿수 합이 딱 나누어떨어집니다.
1+2+…+44 = (44 · 45)/2 = 990 = 9 × 110 ≡ 0 (mod 9)
10의 거듭제곱은 모두 9의 배수보다 1 크므로, 어떤 수와 그 자리 숫자 합은 항상 같은 나머지를 갖는다.
어떤 수와 그 자릿수의 합은 9로 나눈 나머지가 언제나 같다.
▸ 왜?
모든 자리의 값은 9의 배수보다 하나 크므로, 나눗셈에서는 자릿수의 합만 살아남는다.
배수 판정은 자리값에서 나온다10, 100, 1000이 나누는 수와 정해진 관계에 있어 특정 자리만 문제가 된다 — 끝 두 자리가 4를, 자릿수의 합이 3과 9를 정한다.
▸ 왜?
나누는 수를 인수를 공유하지 않는 조각으로 가르면, 각 조각을 따로 시험할 수 있다.
최소공배수두 수의 공배수는 그 최소공배수의 배수들과 정확히 같고, 두 주기는 LCM에서 처음 만난다.
4STEP 4
두 단서 합치기
두 단서를 합치면 9입니다.
x ≡ 0 (mod 9), x ≡ 4 (mod 5) → x ∈ {0,9,18,27,36}, x=9
45보다 작은 9의 배수 중 5의 배수에서 4만큼 떨어진 수는 하나뿐이라 그것이 답이다.
4.OA.B.4Eliminate Possibilities정답
9
나머지 9는 45보다 작아야 하는데 실제로 그렇다. 두 조각으로 빠르게 점검하면, 9를 5로 나누면 나머지가 4이고(5로 나눈 단서와 일치), 9는 9의 배수이다(9로 나눈 단서와 일치). 두 조건이 모두 성립하므로 9는 모순이 없다.
💡핵심 정리
거대한 수를 45로 나눌 때는 45를 9와 5로 쪼개라. 끝자리가 5를 맡고 자리 숫자 합이 9를 맡으니, 둘 다 맞는 나머지 하나를 찾으면 된다.
- 45를 9와 5로 쪼개기
- 5로 나눈 나머지
- 9로 나눈 나머지
- 두 단서 합치기