AMC 10 · 2023 · #18

학년 8 number-theory

gcdprime-factorizationdivisibility-ruleslogical-deduction caseworkconvert-to-algebralogical-deduction ↑ 선수 지식: gcdprime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

양의 정수 a, b, c 가 a/14 + b/15 = c/210 를 만족할 때, gcd(a,14), gcd(b,15), gcd(c,210) 에 관한 세 명제 I, II, III 중 항상 참인 것을 모두 고르세요.

답을 골라 클릭하세요.

(A)

$~\text{I, II, and III}$

(B)

$~\text{I only}$

(C)

$~\text{I and II only}$

(D)

$~\text{III only}$

(E)

$~\text{II and III only}$

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

풀이 과정

전략 작은 문제로 쪼개기

세 개의 독립적인 참/거짓 질문이 한 문제 — 도구 #7(작은 문제로 쪼개기) 의 전형. 먼저 양변에 210 을 곱해 c = 15a + 14b 로 정리한 뒤 각 명제를 따로 검증합니다. 도구 #3(가능성 지우기) 으로 반례 하나면 I 을 죽이고, 도구 #13(대수로 바꾸기) — 특히 mod 2, 3, 5, 7 환산 — 으로 III 을 양방향 증명. II 는 "and → or" 라는 논리로 자동 따라옴.

1STEP 1

분모 소거: 14, 15, 210 의 최소공배수는 210, 양변에 곱하면 c = 15a + 14b.

210·a/14 + 210·b/15 = 210·c/210 ⟹ c = 15a + 14b

2STEP 2

I 의 반례: a=1 (gcd(a,14)=1), b=3 이면 c=57=3·19, gcd(57,210)=3≠1 — 명제 I 은 거짓.

a=1, b=3 → c=57, gcd(57,210)=3

3STEP 3

III 정방향: 두 gcd 가 1 이면 c=15a+14b 가 소수 2,3,5,7 어느 것도 안 나눠떨어져 gcd(c,210)=1.

c ≢ 0 (mod 2,3,5,7) ⟹ gcd(c,210)=1

4STEP 4

III 역방향: 항등식으로 gcd(c,14)=gcd(a,14), gcd(c,15)=gcd(b,15) — c 가 210 과 서로소면 둘 다 1.

gcd(c,14)=gcd(a,14), gcd(c,15)=gcd(b,15)

5STEP 5

명제 II 는 약한 '또는' 만 요구 — III 의 역방향 '그리고' 가 이미 줌. 그래서 II 도 참, I 은 거짓이니 II 와 III.

(II, III 참, I 거짓) → (E) II와 III만

정답

~II and III only

III 의 깔끔한 예시 점검: a=1, b=1 이면 c = 15 + 14 = 29 (소수) 이므로 gcd(29, 210) = 1, gcd(1, 14) = gcd(1, 15) = 1 과 일치. 역방향 점검: 210 과 서로소인 c 는 (a, b) 각각이 14, 15 와 서로소인 경우에만 나옴. I 의 반례: a=1, b=3 일 때 c = 57, gcd(57, 210) = 3 ≠ 1 이지만 gcd(1, 14) = 1. 따라서 I 거짓, III 참 (양방향), II 참 (III 의 역보다 약함). 답 (E) II 와 III 만.

💡핵심 정리

양변에 210 을 곱하면 c = 15a + 14b. 각 소수 2, 3, 5, 7 에 대해 mod 환산하면 두 항 중 하나가 사라지므로 gcd(c, 210) = 1 은 gcd(a, 14) = gcd(b, 15) = 1 과 동치 (명제 III). 그 "and" 가 II 의 "or" 를 자동으로 함의하지만, I 은 a = 1, b = 3 에서 c = 57 (3 의 배수) 로 깨짐. 답: (E) II 와 III 만.