공배수란 무엇인가요?
두 자연수의 공배수란 두 수 모두로 나누어떨어지는 수를 말합니다. 예를 들어 12는 4와 6의 공배수인데, \(4 \times 3 = 12\)이고 \(6 \times 2 = 12\)이기 때문입니다. 모든 수는 무한히 많은 배수를 가지므로 두 수가 공유하는 공배수도 무한히 많습니다. 하지만 이 공배수들은 모두 하나의 값, 즉 최소공배수(LCM)를 바탕으로 한 단순한 규칙을 따릅니다.
계산기 사용 방법
두 수를 입력하고 몇 개의 공배수를 보고 싶은지 선택하면, 계산기가 최소공배수(LCM), 최대공약수(GCD), 그리고 작은 순서대로 정렬된 공통 배수 목록을 보여줍니다. 모든 공배수는 LCM의 배수이므로, 목록은 단순히 LCM, 2×LCM, 3×LCM … 순으로 이어집니다.
공식 풀이
공배수를 가장 빠르게 구하는 길은 LCM을 거치는 것입니다. LCM은 GCD로부터 구할 수 있습니다.
$$\operatorname{lcm}(\text{a},\, \text{b}) = \frac{\text{a} \times \text{b}}{\gcd(\text{a},\, \text{b})}$$GCD는 유클리드 호제법으로 계산하는데, 큰 수를 작은 수로 나눈 나머지로 큰 수를 계속 바꿔 가는 방식입니다. LCM을 구하고 나면 모든 공배수는 \(k = 1, 2, 3, \ldots\) 에 대해 \(k \times \operatorname{lcm}\) 으로 나타낼 수 있습니다.
$$M_k = \operatorname{lcm}(\text{a},\, \text{b}) \times k, \quad k = 1, 2, \ldots, \text{Count}$$
예제 풀이
\(a = 4\), \(b = 6\) 이라고 해 봅시다. 두 수의 GCD는 2이므로 다음과 같습니다.
$$\operatorname{lcm} = \frac{4 \times 6}{2} = \frac{24}{2} = 12$$따라서 처음 다섯 개의 공배수는 12, 24, 36, 48, 60 이며, 모두 4와 6 양쪽으로 나누어떨어집니다.
자주 묻는 질문
가장 큰 공배수가 있나요? 없습니다. LCM에 계속 곱해 나갈 수 있으므로 공배수는 끝없이 이어집니다. 오직 가장 작은 공배수, 즉 LCM만 존재합니다.
두 수가 같으면 어떻게 되나요? 이 경우 LCM은 그 수와 같아지고, 공배수는 그 수의 일반적인 배수가 됩니다.
한 수가 1이면 어떻게 되나요? 1은 모든 수를 나누므로, 다른 수의 모든 배수가 곧 공배수가 됩니다.
