최대공약수·최소공배수 계산기란?
이 계산기는 두 자연수에 대해 가장 기본이 되는 두 가지 값을 구합니다. 바로 최대공약수(GCF, Greatest Common Factor) — 흔히 최대공약수(GCD)라고도 부릅니다 — 와 최소공배수(LCM, Least Common Multiple)입니다. 최대공약수는 두 입력값을 모두 나누어떨어지게 하는 가장 큰 수이고, 최소공배수는 두 입력값으로 모두 나누어떨어지는 가장 작은 수입니다. 이 값들은 분수를 약분하거나 통분할 때, 그리고 정수론 문제를 풀 때 끊임없이 등장합니다.
사용 방법
첫 번째 수와 두 번째 수 칸에 두 자연수를 입력한 뒤 계산 버튼을 누르세요. 계산기는 상단 결과창에 최대공약수를 보여 주고, 아래 표에는 최소공배수와 두 수의 곱을 함께 표시합니다. 두 값 모두 유클리드 호제법으로 즉시 계산되며, 아주 큰 수에서도 빠르게 동작합니다.
계산 공식 풀이
최대공약수는 유클리드 호제법으로 구합니다. \((a,\ b)\) 쌍을 \((b,\ a \bmod b)\)로 계속 바꿔 나가다가 두 번째 값이 0이 되면, 남은 값이 바로 최대공약수입니다. 최대공약수를 구하고 나면 최소공배수는 다음의 깔끔한 관계식으로 바로 얻을 수 있습니다.
$$\text{LCM}(a,\ b) = \frac{a \times b}{\text{GCF}(a,\ b)}$$
이는 두 수의 곱이 언제나 그 두 수의 최대공약수와 최소공배수의 곱과 같기 때문입니다.
예제로 보기
\(a = 12\), \(b = 18\) 인 경우를 살펴봅시다. 유클리드 호제법을 적용하면 \(18 \div 12\)의 나머지는 6, 다시 \(12 \div 6\)의 나머지는 0이므로 최대공약수는 6입니다. 그러면 최소공배수는 $$\frac{12 \times 18}{6} = \frac{216}{6} = 36$$ 이 됩니다. 따라서 \(\text{GCF}(12,\ 18) = 6\), \(\text{LCM}(12,\ 18) = 36\) 입니다.
자주 묻는 질문
GCF와 GCD는 어떻게 다른가요? 사실 같은 개념입니다. "최대공약수(greatest common factor)"와 "최대공약수(greatest common divisor)"는 서로 바꿔 쓸 수 있는 표현입니다.
소수(소수점 수)도 입력할 수 있나요? 최대공약수와 최소공배수는 정수(자연수)에 대해 정의됩니다. 소수점 수는 계산 전에 정수로 내림 처리됩니다.
한 수가 0이면 어떻게 되나요? 수학적으로 어떤 수와 0의 최대공약수는 그 수 자체이지만, 최소공배수는 정의되지 않습니다. 의미 있는 결과를 얻으려면 양의 자연수를 사용하세요.
