최대공약수와 최소공배수

정수 $a, b$ 에 대해, $d$ 가 $a ∣ d$ 와 $b ∣ d$ 를 동시에 만족하는 (양의) 정수 중 가장 큰 값을 $a$ 와 $b$ 의 최대공약수라고 한다. 이 최대공약수를 기호로는

(a, b) 또는 g cd (a, b)

로 쓴다.

또한, $a ∣ c$ 와 $b ∣ c$ 를 동시에 만족하는 양의 정수 $c$ 중 가장 작은 값을 $a$ 와 $b$ 의 최소공배수라고 하며,
기호로는

[a, b] 또는 lcm (a, b)

로 쓴다.

최대공약수가 1일 때, 즉

(a, b) = 1

이면, $a$ 와 $b$ 가 서로소(relatively prime) 라고 한다.

최대공약수와 최소공배수의 곱

ab = (a, b) [a, b]

$a = d a^{'}$ , $b = d b^{'}$ 이라고 두자. 여기서, $(a^{'}, b^{'}) = 1$ (즉, 서로소)라고 하자. 그러면,

(a, b) = d

이고

[a, b] = d a^{'} b^{'}

이므로

ab = d \cdot d a^{'} b^{'} = (a, b) [a, b]

가 성립한다.

풀이

최대 공약수를 고려하여 결정
- $ab$ 와 $b c$ 를 비교하면, $b = 2^{2} \cdot 3^{2}$ 를 최대로 가짐.
- $b c$ 와 $c d$ 를 비교하면, $c = 2^{2} \cdot 3$ 를 최대로 가짐.
- $c d$ 와 $d e$ 를 비교하면, $d = 2^{2} \cdot 5$ 를 최대로 가짐.
위의 조건을 고려하여 가능한 자연수 조합은

(2^{2} \cdot 3^{2}, 2, 3, 2^{2} \cdot 5, 5^{2})

이므로, 가능한 자연수의 순서쌍은 다음과 같다.

$12$ 와 $30$ 의 최대공약수와 최소공배수를 구하여라. ¹
자연수 $1, 2, 3, \dots, 30$ 의 최소공배수를 구하여라. ²
모든 홀수의 제곱은 $8 q + 1$ 꼴임을 보여라. ( $q$ 는 정수) ³
$g cd (a, b) = 1$ 이고 $c ∣ (a + b)$ 이면, $g cd (a, c) = g cd (b, c) = 1$ 임을 증명하여라. ⁴
$5$ 개의 자연수 $a, b, c, d, e$ 에서 $a$ 와 $b$ 의 곱은 $72$ , $b$ 와 $c$ 의 곱은 $108$ , $c$ 와 $d$ 의 곱은 $60$ , $d$ 와 $e$ 의 곱은 $500$ 을 만족시키는 자연수의 순서쌍 $(a, b, c, d, e)$ 를 모두 구하여라. ⁵

$12 = 2^{2} \times 3$ , $30 = 2 \times 3 \times 5$ 이므로, $(12, 30) = 2 \times 3 = 6$ , $[12, 30] = 2^{2} \times 3 \times 5 = 60$ 이다. ↩
$2^{4} \times 3^{2} \times 5^{2} \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29$ 이다. ↩
모든 홀수는 $2 k + 1$ 꼴이므로, $(2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 4 k (k + 1) + 1$ 이다. $k$ 와 $k + 1$ 중 하나는 짝수이므로 $q = \frac{k ( k + 1 )}{2}$ 로 놓으면, $(2 k + 1)^{2} = 8 q + 1$ 이 성립한다. ↩
$d = g cd (a, c)$ 라 하자. $d ∣ a$ 이므로 $d ∣ (a + b)$ . 그런데 $g cd (a, b) = 1$ 이므로 $d ∣ b$ 도 성립한다. 따라서 $d = 1$ 이 된다. 동일한 방법으로 $g cd (b, c) = 1$ 임을 알 수 있다. ↩
$ab = 72 = 2^{3} \cdot 3^{2}$ , $b c = 108 = 2^{2} \cdot 3^{3}$ , $c d = 60 = 2^{2} \cdot 3 \cdot 5$ , $d e = 500 = 2^{2} \cdot 5^{3}$ 이므로, $b = 2^{2} \cdot 3^{2}$ , $c = 2^{2} \cdot 3$ , $d = 2^{2} \cdot 5$ 를 최대로 가진다. $3 ∣ c d$ 이고 $3^{2} ∣ c d$ 이므로 $3^{2} ∣ b$ 이다. $3 ∤ d e$ 이고 $3 ∤ d$ 이므로 $3 ∣ c$ 이다. $5 ∤ b c$ 이므로 $5 ∤ c$ , 따라서 $5 ∣ d$ 이다. 따라서 가능한 조합은 $(2^{3}, 3^{2}, 2^{2} \cdot 3, 5, 2^{2} \cdot 5^{2})$ , $(2^{2} \cdot 3^{2}, 3, 2^{2} \cdot 5, 5, 2^{2} \cdot 5^{2})$ , $(2^{2} \cdot 3^{2}, 2, 3, 2^{2} \cdot 5, 5^{2})$ 이다. ↩