두 수의 최대공약수와 두 수의 합은 무슨 관계가 있을까

1. 문제 25375번: 아주 간단한 문제 (acmicpc.net) 25375번: 아주 간단한 문제 양의 정수 $a$, $b$가 주어지면, $gcd(x, y) = a$이고 $x + y = b$인 자연수 쌍 $(x, y)$가 존재하는지의 여부를 출력하자. www.acmicpc.net 2. 풀이 gcd(x,y) = a라는 것은 x,y가 a의 배수라는 것이다. ( a >= 1) 즉 x,y는 어떤 자연수 $k_{1}$와 $k_{2}$에 대하여 $$x = ak_{1}$$ $$y = ak_{2}$$ 그러므로 x+y = b를 a로 나눈다면.. $$k_{1} + k_{2} = \frac{b}{a}$$ 여기서 $k_{1}$와 $k_{2}$이 자연수이므로 우변 $\frac{b}{a}$는 자연수이다. 그러므로 자연수 쌍 (..