문제 · Page 0
단계별로 풀어볼까요?
정답은 마지막에 확인해요. 먼저 스스로 생각해보고, 막히면 다음 단계로 넘어가세요.
📖 핵심 표현:
$\gcd(A,B) = g$이면 $A = g \cdot m$, $B = g \cdot n$ (단, $\gcd(m, n) = 1$, 즉 $m, n$ 서로소). 이 표현이 GCD 문제의 만능 기술이에요.
유형 5 · H2
두 자연수 $A$, $B$의 $\gcd(A, B) = 6$이고, $A + B = 90$일 때, 가능한 $(A, B)$ 쌍의 수를 구하세요. (단, $A < B$)
🤔 잠깐, 손으로 생각해보세요
$A = 6m$, $B = 6n$으로 놓으면 무엇이 보일까요? $m + n$ 값과 $m, n$이 서로소라는 조건을 함께 생각해봐요.
1단계 · Page 1
$A, B$를 $\gcd$로 표현
왜 이 단계? — GCD 정보를 변수에 직접 녹여 넣으면 식이 간단해져요.
표현
$\gcd(A, B) = 6$ ⟹ $A = 6m$, $B = 6n$ ($m, n$은 자연수, $\gcd(m, n) = 1$)
또 $A < B$이므로 $m < n$.
조건 $A + B = 90$ 적용
$6m + 6n = 90$
$6(m + n) = 90$
$m + n = 15$
2단계 · Page 2
$m + n = 15$ 만족하는 $(m, n)$ 쌍 찾기
왜 이 단계? — $m < n$, $\gcd(m, n) = 1$ 모두 만족하는 쌍을 모두 골라야 해요.
탐색표
| $m$ | $n$ | $\gcd(m, n)$ | 서로소? |
|---|
| 1 | 14 | 1 | ✅ |
| 2 | 13 | 1 | ✅ |
| 3 | 12 | 3 | ✗ |
| 4 | 11 | 1 | ✅ |
| 5 | 10 | 5 | ✗ |
| 6 | 9 | 3 | ✗ |
| 7 | 8 | 1 | ✅ |
유효한 쌍: $(1, 14), (2, 13), (4, 11), (7, 8)$ → 4쌍
(이 다음 $m=8, n=7$은 $m < n$ 조건 위반이므로 멈춤.)
3단계 · Page 3
실제 $(A, B)$ 쌍 확인
왜 이 단계? — $A = 6m$, $B = 6n$으로 환원해 답이 잘 나오는지 검산.
$(A, B)$ 계산
| $(m, n)$ | $A = 6m$ | $B = 6n$ | $\gcd$ | $A+B$ |
|---|
| (1, 14) | 6 | 84 | 6 ✅ | 90 ✅ |
| (2, 13) | 12 | 78 | 6 ✅ | 90 ✅ |
| (4, 11) | 24 | 66 | 6 ✅ | 90 ✅ |
| (7, 8) | 42 | 48 | 6 ✅ | 90 ✅ |
모두 $\gcd = 6$, 합 $= 90$ ✅
⚠️ 흔한 실수
$m + n = 15$만 풀고 $7$쌍이라 답하면 틀려요! 서로소 조건을 잊으면 $\gcd$가 $6$보다 커져버려요. (예: $m=3, n=12$이면 $\gcd(A,B) = 6 \times 3 = 18$이 됨)
정답 · Page ★
정답 + 풀이 흐름 요약
📖 핵심 기법:
"$\gcd(A,B) = g$" → $A = gm$, $B = gn$ with $\gcd(m,n) = 1$. 이 형태가 GCD 문제의 만능 도구.
$4$쌍
$(6, 84), (12, 78), (24, 66), (42, 48)$
전체 풀이 흐름 — 4단계
1
$A = 6m$, $B = 6n$ ($\gcd(m, n) = 1$, $m < n$)로 설정
2
$A + B = 90$ → $m + n = 15$
3
$m + n = 15$, $m < n$, $\gcd(m,n) = 1$ 만족: $(1,14), (2,13), (4,11), (7,8)$ — 4쌍
4
검산: 모두 $\gcd = 6$, 합 $= 90$ ✅
⚠️ 이 유형의 핵심 함정
서로소 조건을 잊지 마요. 빠뜨리면 GCD가 약속한 값보다 커지는 쌍이 답에 섞여요.