AMC 10 · 2018 · #23

학년 7 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor-Pair Enumeration

gcdlcmsimons-favorite-factoring-trick convert-to-algebrasimons-favorite-factoring-tricksystematic-enumeration ↑ 선수 지식: gcdlcm

📏 중간 풀이 💡 3 개 인사이트

문제

a· b + 63 = 20 lcm(a,b) + 12 gcd(a,b)를 만족하는 양의 정수 순서쌍 (a,b)의 개수를 구한다. "순서쌍"이므로 a ≠ b일 때 (a,b)와 (b,a)는 따로 센다.

답을 골라 클릭하세요.

(A)

$text{ 0}$

(B)

$text{ 2}$

(C)

$text{ 4}$

(D)

$text{ 6}$

(E)

$text{ 8}$

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

풀이 과정

전략 대수로 바꾸기

도구 #4 (변수 도입하기): 복잡한 두 양을 g=gcd(a,b), l=lcm(a,b)로 이름 붙여 방정식이 a와 b를 직접 다루지 않게 한다. 도구 #13 (대수로 바꾸기): 항등식 ab=g l이 전체를 g와 l에 대한 깔끔한 방정식으로 바꾸고, 사이먼이 가장 좋아하는 인수분해 기법(SFFT)이 이를 곱 (g-20)(l-12)=177로 만든다. 도구 #2 (빠짐없이 나열하기): 177의 약수는 몇 개 안 되므로 모든 후보 (g,l)을 빠짐없이 적을 수 있다. 도구 #3 (가능성 지우기): gcd는 반드시 자신의 lcm을 나눠야 한다는 구조적 규칙이 하나만 남기고 모든 후보를 버리며, 그 뒤 실제 쌍을 세는 일은 금방 끝난다.

1STEP 1

gcd와 lcm을 g와 l로 이름 붙이기

g=gcd(a,b), l=lcm(a,b)로 두면 ab=g·l이므로 정수론 방정식이 g와 l의 깔끔한 식 gl+63=20l+12g가 된다.

ab=g l → g l+63=20 l+12 g

2STEP 2

사이먼의 기법으로 인수분해하기

모두 한쪽으로 모으고 240을 더하면 사이먼의 인수분해 기법(SFFT)으로 (g-20)(l-12)=177이 된다.

(g-20)(l-12)=177

3STEP 3

177의 약수쌍 나열하기

177=3×59의 약수쌍 넷이 후보 (g,l)=(21,189),(23,71),(79,15),(197,13)을 주고, 음의 쌍은 불가능하다.

(g-20, l-12)∈{(1,177),(3,59),(59,3),(177,1)}

4STEP 4

g가 l을 나누는 쌍만 남기기

gcd는 lcm을 나눠야 하므로 189=21·9인 (g,l)=(21,189)만 통과하고, 23∤71, 79∤15, 197∤13은 탈락.

21 ∣ 189 ✓, 23 ∤ 71, 79 ∤ 15, 197 ∤ 13

5STEP 5

g=21, l=189에서 순서쌍 세기

a=gx, b=gy, gcd(x,y)=1이면 xy=9라 (x,y)=(1,9),(9,1)뿐이므로 순서쌍 2개: (21,189)·(189,21).

xy=189/21=9, gcd(x,y)=1 → (x,y)=(1,9),(9,1) → 2개

정답

text{ 2}

남은 쌍을 원래 방정식에 넣어 확인한다. (a,b)=(21,189): gcd=21, lcm=189, ab=3969. 좌변 =3969+63=4032; 우변 =20·189+12·21=3780+252=4032. 일치하며, 대칭성에 의해 (189,21)도 성립한다. 다른 (g,l)은 나눗셈 검사를 통과하지 못했으므로 정확히 2개가 존재한다. 서로 다른 해가 거울처럼 둘씩 짝지어 나오므로 개수가 짝수인 것도 자연스럽고, 이는 보기 (B)와 일치한다.

💡핵심 정리

gcd와 lcm에 이름을 붙이고, 그 곱이 ab임을 쓰고, 사이먼의 기법으로 인수분해하면, gcd가 lcm을 나누는 약수쌍만 살아남아 순서쌍 2개가 된다.

gcd와 lcm을 g와 l로 이름 붙이기
사이먼의 기법으로 인수분해하기
177의 약수쌍 나열하기
g가 l을 나누는 쌍만 남기기
g=21, l=189에서 순서쌍 세기

gcd와 lcm을 g와 l로 이름 붙이기

사이먼의 기법으로 인수분해하기

177의 약수쌍 나열하기

g가 l을 나누는 쌍만 남기기

g=21, l=189에서 순서쌍 세기

비슷한 유형 더 풀어보기