AMC 10 · 2018 · #22

학년 6 number-theory

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

gcdprime-factorizationdivisibility-rules caseworkbound-inequality-then-enumerate ↑ 선수 지식: gcdprime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

양의 정수 a,b,c,d가 gcd(a,b)=24, gcd(b,c)=36, gcd(c,d)=54, 그리고 70 ＜ gcd(d,a) ＜ 100을 만족한다. 보기 5,7,11,13,17 중 반드시 a의 약수가 되어야 하는 것을 고른다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 변수 도입하기

gcd은 소수를 하나씩 따로 다룬다. 즉 각 소수에 대해 두 수의 지수 중 더 작은 값을 남긴다. 그래서 도구 #4(변수 도입하기): e_p(x)를 x에 들어 있는 소수 p의 지수로 두면, 모든 gcd 정보가 '두 지수 중 작은 값' 이라는 단순한 진술로 바뀐다. 도구 #7(작은 문제로 쪼개기): 소수 2와 소수 3은 서로 간섭하지 않으므로 따로 다루어 a 안의 2의 거듭제곱과 3의 거듭제곱을 정확히 확정한다. 그러면 gcd(d,a)는 6에 (2나 3을 인수로 갖지 않는 수)를 곱한 형태로 고정된다. 도구 #3(가능성 지우기): 70 ＜ x ＜ 100 범위에서 그 조건을 통과하는 6의 배수는 단 하나뿐이며, 그것이 a에 강제되는 소수를 드러낸다.

1STEP 1

소인수분해하고 지수에 이름 붙이기

소수 2와 3만 등장한다. e_p(x)를 지수로 두면 gcd은 각 소수의 더 작은 지수를 남긴다는 규칙이 핵심이다.

24=2³·3, 36=2²·3², 54=2·3³

2STEP 2

더 작은 지수 규칙 적기

더 작은 지수를 읽으면 네 gcd이 여섯 개의 min 식이 된다: 소수 2는 min이 3, 2, 1, 소수 3은 1, 2, 3이다.

min(e₂(a),e₂(b))=3, min(e₂(b),e₂(c))=2, min(e₂(c),e₂(d))=1

3STEP 3

2의 거듭제곱 따라가기

e₂(b) ≥ 3이라 e₂(c)=2, 이어 e₂(d)=1이 강제되고, a는 e₂(a) ≥ 3을 유지한다.

e₂(b) ≥ 3→ e₂(c)=2→ e₂(d)=1, e₂(a) ≥ 3

4STEP 4

3의 거듭제곱 따라가기

대칭적으로 e₃(b) ≥ 2가 e₃(a)=1을 강제하고, min(e₃(c),e₃(d))=3에서 e₃(d) ≥ 3: a는 3을 하나 가진다.

e₃(b) ≥ 2→ e₃(a)=1, e₃(d) ≥ 3

5STEP 5

gcd(d,a) 만들기

d와 a를 비교하면 2는 min(1, ≥ 3)=1, 3은 min( ≥ 3,1)=1이므로 gcd(d,a)=6m이고 m은 6과 서로소다.

gcd(d,a)=2¹·3¹· m=6m, gcd(m,6)=1

6STEP 6

범위로 값 못 박기

70 ＜ 6m ＜ 100이라 m∈{12,…,16}, 짝수와 3의 배수를 빼면 m=13이므로 gcd(d,a)=78이 a를 나눈다: 답 (D).

70 ＜ 6m ＜ 100→ m=13→ gcd(d,a)=78→ 13 ∣ a

정답

강제된 값 gcd(d,a)=78=2·3·13은 실제로 70과 100 사이에 있고 78이 a를 나누므로 13 ∣ a이다. 구체적인 예가 가능함을 확인한다: a=2³·3·13=312, b=2³·3²=72, c=2²·3³=108, d=2·3³·13=702로 두면 gcd(a,b)=24, gcd(b,c)=36, gcd(c,d)=54, gcd(d,a)=78로 모두 들어맞는다. 다른 보기는 강제되지 않는다: 조건은 a가 5, 7, 11, 17을 가질 것을 요구하지 않는다.

💡핵심 정리

gcd은 각 소수의 더 작은 거듭제곱을 남기므로 2와 3을 따로 추적하라: 그러면 gcd(d,a)=6m이 강제되고, 70과 100 사이에 맞는 것은 78=6·13뿐이라 13이 반드시 a를 나눈다 — 보기 (D).

소인수분해하고 지수에 이름 붙이기
더 작은 지수 규칙 적기
2의 거듭제곱 따라가기
3의 거듭제곱 따라가기
gcd(d,a) 만들기
범위로 값 못 박기