AMC 10 · 2023 · #18

학년 8 number-theory

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

📏 긴 풀이 💡 3 개 인사이트

문제

Suppose $a$ , $b$ , and $c$ are positive integers such that $\frac{a}{14}+\frac{b}{15}=\frac{c}{210}.$ Which of the following statements are necessarily true?

I. If $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both, then $\gcd(c,210)=1$ .

II. If $\gcd(c,210)=1$ , then $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both.

III. $\gcd(c,210)=1$ if and only if $\gcd(a,14)=\gcd(b,15)=1$ .

답을 골라 클릭하세요.

(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.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

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

주어진 것: $\dfrac{a}{14} + \dfrac{b}{15} = \dfrac{c}{210},\ a, b, c \in \mathbb{Z}_{>0}$; $210 = 2 \cdot 3 \cdot 5 \cdot 7,\ 14 = 2 \cdot 7,\ 15 = 3 \cdot 5$; 명제 I: $\gcd(a,14)=1$ 또는 $\gcd(b,15)=1$ $\Rightarrow$ $\gcd(c,210)=1$; 명제 II: $\gcd(c,210)=1$ $\Rightarrow$ $\gcd(a,14)=1$ 또는 $\gcd(b,15)=1$; 명제 III: $\gcd(c,210)=1$ iff $\gcd(a,14)=\gcd(b,15)=1$; 선택지: (A) I, II, III; (B) I만; (C) I과 II; (D) III만; (E) II와 III만

구하는 것: $\{$I, II, III$\}$ 중 반드시 참인 명제의 집합

이해

계획

주요 도구: #7 작은 문제로 쪼개기

보조 도구: #3 가능성 지우기, #13 대수로 바꾸기

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

실행 — 정답: E

#13 대수로 바꾸기 6.NS.B.4 단계 1

분모 소거.
$14, 15, 210$ 의 최소공배수는 $210$.
양변에 $210$ 을 곱하면 분수 방정식이 깔끔한 정수 일차 관계로 바뀝니다.

$$210\cdot\dfrac{a}{14} + 210\cdot\dfrac{b}{15} = 210\cdot\dfrac{c}{210} \;\Longrightarrow\; c = 15a + 14b$$

💡 $c = 15a + 14b$ 가 분수보다 다루기 훨씬 쉬움 — $15 = 3 \cdot 5$, $14 = 2 \cdot 7$ 의 서로소 분리가 소수별로 깔끔히 갈리리라는 신호.

#3 가능성 지우기 6.NS.B.4 단계 2

명제 I 을 가장 작은 반례로 검증.
$a = 1$ 로 두면 $\gcd(a, 14) = 1$ (가정 만족).
$b = 3$ 으로 두면 $c = 15(1) + 14(3) = 57 = 3 \cdot 19$.
그런데 $\gcd(c, 210) = \gcd(57, 210) = 3 \ne 1$ — 결론 실패.
따라서 명제 I 은 거짓.

$$a=1,\ b=3 \Rightarrow c=57,\ \gcd(57,210)=3$$

💡 보편 명제는 반례 하나면 끝 — $a$ 로 가정을 채우고, $b$ 로 $c$ 에 금지된 소수를 슬쩍 끼워 넣음.

#7 작은 문제로 쪼개기 8.EE.C.7 단계 3

명제 III 의 정방향 증명: $\gcd(a, 14) = 1$ 과 $\gcd(b, 15) = 1$ 이면 $c = 15a + 14b$ 가 $\{2, 3, 5, 7\}$ 의 모든 소수를 피함.
mod $2$: $c \equiv a \pmod 2$, $\gcd(a,14)=1$ 이면 $a$ 가 홀수.
mod $7$: $c \equiv a \pmod 7$, $7\nmid a$.
mod $3$: $c \equiv 2b \pmod 3$, $3\nmid b$.
mod $5$: $c \equiv 4b \pmod 5$, $5\nmid b$.

$$c \not\equiv 0 \pmod{2,3,5,7} \;\Longrightarrow\; \gcd(c,210)=1$$

💡 $c = 15a + 14b$ 를 각 소수로 환산하면 두 항 중 하나가 사라져 한 변수만 보면 됨 — 케이스마다 한 줄 점검.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 4

명제 III 의 역방향 증명: $\gcd(x + ky, y) = \gcd(x, y)$ 라는 항등식을 사용.
mod $14$: $\gcd(c, 14) = \gcd(15a + 14b, 14) = \gcd(15a, 14) = \gcd(a, 14)$ (∵ $\gcd(15, 14) = 1$).
mod $15$: $\gcd(c, 15) = \gcd(14b, 15) = \gcd(b, 15)$.
따라서 $\gcd(c, 210) = 1$ 이면 $\gcd(c, 14) = \gcd(c, 15) = 1$, 즉 $\gcd(a, 14) = \gcd(b, 15) = 1$.

$$\gcd(c,14)=\gcd(a,14),\quad \gcd(c,15)=\gcd(b,15)$$

💡 $14b$ 항은 mod $14$ 에서 $0$, $15 \equiv 1 \pmod{14}$ 이므로 $\gcd(c, 14) = \gcd(a, 14)$ — 반대편도 같은 요령.

#3 가능성 지우기 6.NS.B.4 단계 5

명제 II 마무리.
명제 III 의 역방향이 $\gcd(c,210)=1 \Rightarrow \gcd(a,14)=1$ "그리고" $\gcd(b,15)=1$ 을 줌.
"그리고" 가 참이면 "또는" 도 자동으로 참 — 그래서 II 도 참.
결국 II 와 III 만 항상 참.

$$\text{(II, III 참, I 거짓)} \;\Rightarrow\; \textbf{(E) }\text{II와 III만}$$

💡 논리에서 "and" 가 "or" 보다 강함 — 어려운 "and" 를 III 으로 증명했으니 약한 "or" 인 II 는 덤.

[1] #13 6.NS.B.4 분모 소거. $14, 15, 210$ 의 최소공배수는 $210$. 양변에 $210$ 을 곱하면 분수 방정식이 깔끔한 정수 일차 관계로 바뀝니다.

[2] #3 6.NS.B.4 명제 I 을 가장 작은 반례로 검증. $a = 1$ 로 두면 $\gcd(a, 14) = 1$ (가정 만족). $b = 3$ 으로 두면 $c =

[3] #7 8.EE.C.7 명제 III 의 정방향 증명: $\gcd(a, 14) = 1$ 과 $\gcd(b, 15) = 1$ 이면 $c = 15a + 14b$ 가 ${2

[4] #7 6.NS.B.4 명제 III 의 역방향 증명: $\gcd(x + ky, y) = \gcd(x, y)$ 라는 항등식을 사용. mod $14$: $\gcd(c, 1

[5] #3 6.NS.B.4 명제 II 마무리. 명제 III 의 역방향이 $\gcd(c,210)=1 \Rightarrow \gcd(a,14)=1$ "그리고" $\gcd(b,

검토

합리성 확인: 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 \ne 1$ 이지만 $\gcd(1, 14) = 1$. 따라서 I 거짓, III 참 (양방향), II 참 (III 의 역보다 약함). 답 (E) II 와 III 만.

대안 접근: 도구 #5(패턴 찾기) — 작은 $(a, b)$ 를 표로 나열해 $c$ 와 네 개의 gcd 를 직접 계산. 예: $(a, b) \in \{(1,1), (1,3), (2,1), (7,15)\}$ 면 $c \in \{29, 57, 44, 315\}$, $\gcd(c, 210) \in \{1, 3, 2, 105\}$. 패턴 $\gcd(c,14) = \gcd(a, 14)$, $\gcd(c, 15) = \gcd(b, 15)$ 가 경험적으로 떠올라 같은 결론 (E).

사용된 CCSS 표준 (최저 학년 8)

6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 (I 반례에서 $\gcd(57, 210) = 3$ 같은 구체 gcd 계산, 그리고 $\gcd(x + ky, y) = \gcd(x, y)$ 항등식을 적용해 $\gcd(c, 14)$ 와 $\gcd(a, 14)$ 를 잇는 데 사용.)
8.EE.C.7 한 변수 일차방정식 풀기 ($c = 15a + 14b$ 를 $\{2, 3, 5, 7\}$ 각 소수로 환산해 한 변수 합동식 (예: $c \equiv a \pmod 7$) 으로 만들어 나눠떨어짐을 판단.)

⭐ 양변에 $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$ 의 배수) 로 깨짐. 답: $\textbf{(E) }$II 와 III 만.