최대공약수·최소공배수 계산기

계산 입력

정수 (쉼표 또는 공백으로 구분) 양의 정수를 두 개 이상 입력하세요. 예: 12, 18, 24

결과

최대공약수 (GCD)

6

GCF / HCF 라고도 함

최소공배수 (LCM)

72

가장 작은 공배수

입력한 수	3
계산 방법	유클리드 호제법

이 계산기로 할 수 있는 일

이 도구는 두 개 이상의 정수에 대해 정수론에서 핵심이 되는 두 가지 값을 구해 줍니다. 바로 최대공약수(GCD) — 영어로는 Greatest Common Factor(GCF)나 Highest Common Factor(HCF)라고도 부릅니다 — 와 최소공배수(LCM)입니다. 최대공약수는 입력한 모든 수를 나누어떨어지게 하는 가장 큰 양의 정수이고, 최소공배수는 입력한 모든 수가 나머지 없이 나누어떨어지는 가장 작은 양의 정수입니다. 이 두 값은 분수의 약분과 통분, 일정 주기 계산, 기어비, 암호학 등 다양한 분야에서 쓰입니다.

사용 방법

두 개 이상의 양의 정수를 쉼표나 공백으로 구분해 입력한 뒤 계산하세요. 예를 들어 12, 18, 24처럼 적으면 됩니다. 음수는 절댓값으로 변환되고, 소수는 가장 가까운 정수로 반올림됩니다. 계산기는 최대공약수와 최소공배수를 한 번에 함께 보여 줍니다. 입력값 중 0이 있으면 최소공배수는 0으로 표시됩니다. 0은 다른 수와 공통되는 양의 배수를 갖지 않기 때문입니다.

계산 원리

두 수의 최대공약수는 유클리드 호제법으로 구합니다. \((a, b)\) 쌍을 \((b, a \bmod b)\)로 계속 바꿔 나가다가 두 번째 값이 0이 되면, 그때 남은 첫 번째 값이 바로 최대공약수입니다. 최소공배수는 여기서 \((a / \text{최대공약수}) \times b\)로 구하는데, 이 순서는 오버플로를 줄이기 위해 선택한 것입니다. 세 개 이상의 수는 두 개씩 차례로 계산합니다. 즉, 지금까지의 결과와 다음 수를 묶어 계산하고, 또 그 결과를 다음 수와 묶는 식으로 이어 갑니다.

$$\gcd(a_1,\dots,a_k), \qquad \operatorname{lcm}(a_1,\dots,a_k) = \frac{|a_i \cdot a_j|}{\gcd(a_i,a_j)}$$

공통 소인수가 최대공약수를 이루고, 모든 인수를 합치면 최소공배수가 됩니다.

유클리드 호제법은 나머지가 0이 될 때까지 쌍을 반복해서 바꿉니다.

예제로 풀어 보기

12, 18, 24를 예로 들어 봅시다. 먼저 \(\gcd(12, 18) = 6\)이고, 다음으로 \(\gcd(6, 24) = 6\)이므로 최대공약수는 6입니다. 최소공배수는 \(\operatorname{lcm}(12, 18) = 12 \times 18 / 6 = 36\), 이어서 \(\operatorname{lcm}(36, 24) = 36 \times 24 / 12 = 72\)이므로 최소공배수는 72입니다. 검산해 보면 \(72 \div 12 = 6\), \(72 \div 18 = 4\), \(72 \div 24 = 3\)으로 모두 나누어떨어지고, 6 역시 세 입력값을 모두 나눕니다.

자주 묻는 질문

GCD는 GCF나 HCF와 같은 건가요? 네, 같습니다. Greatest Common Divisor(최대공약수), Greatest Common Factor, Highest Common Factor는 모두 같은 값을 가리키는 다른 이름일 뿐입니다.

두 수에 공통 약수가 없으면 어떻게 되나요? 최대공약수가 1이면 두 수는 서로소입니다. 이때 최소공배수는 단순히 두 수의 곱과 같습니다.

수를 두 개보다 많이 입력해도 되나요? 네. 원하는 만큼 정수를 입력하면 됩니다. 입력한 전체 목록에 대해 최대공약수와 최소공배수를 한꺼번에 계산합니다.