최대공약수 계산기

계산 입력

첫 번째 수 (a)

두 번째 수 (b)

결과

최대공약수

12

GCF of 48 and 36

최대공약수 (GCF)	12
최소공배수 (LCM)	144

최대공약수란?

최대공약수(GCF)는 영어로 greatest common divisor(GCD) 또는 highest common factor(HCF)라고도 불리며, 두 정수를 나머지 없이 나눌 수 있는 가장 큰 양의 정수를 뜻합니다. 예를 들어 48과 36의 최대공약수는 12입니다. 두 수를 모두 나누어떨어지게 하는 가장 큰 수가 바로 12이기 때문이죠. 이 계산기는 최대공약수를 즉시 구해줄 뿐 아니라 최소공배수(LCM)까지 함께 알려줍니다.

최대공약수는 두 수가 공유하는 소인수들의 곱입니다.

계산기 사용법

\(a\)와 \(b\) 입력란에 0 이상의 정수를 각각 입력한 뒤 계산 버튼을 누르세요. 결과로 최대공약수와 최소공배수가 함께 표시됩니다. 두 수의 입력 순서는 결과에 영향을 주지 않습니다. 즉, \(\text{GCF}(48, 36)\)과 \(\text{GCF}(36, 48)\)의 값은 같습니다.

계산 원리

이 계산기는 고대 그리스에서 유래한 우아한 방법인 유클리드 호제법을 사용합니다. 이 방법은 두 수의 최대공약수가 그 두 수를 나눈 나머지도 나눈다는 원리에 기반합니다. \((a, b)\)라는 쌍을 \((b, a \bmod b)\)로 계속 바꿔 나가다가 두 번째 수가 0이 되면, 남은 첫 번째 수가 바로 최대공약수입니다. 최소공배수는 다음 공식으로 구합니다.

$$\text{lcm}(a, b) = \frac{a \times b}{\text{gcf}(a, b)}$$

유클리드 호제법은 \(b\)가 0이 될 때까지 \((a, b)\)를 \((b, a \bmod b)\)로 반복 교체합니다.

예제로 풀어보기

48과 36의 최대공약수를 구해봅시다. 1단계: \(48 \bmod 36 = 12\)이므로 쌍은 \((36, 12)\)가 됩니다. 2단계: \(36 \bmod 12 = 0\)이므로 쌍은 \((12, 0)\)이 됩니다. 두 번째 값이 0이 되었으니 최대공약수는 12입니다. 최소공배수는 다음과 같습니다.

$$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$

자주 묻는 질문

한쪽 수가 0이면 최대공약수는 얼마인가요? 정의에 따라 \(\text{GCF}(a, 0) = a\)입니다. 그리고 0과 0의 최대공약수는 0입니다.

GCF와 HCF는 같은 건가요? 네, 같습니다. GCF, GCD, HCF는 모두 같은 값을 가리키는 다른 이름일 뿐입니다.

두 수가 공약수를 갖지 않으면 최대공약수는 얼마인가요? 이 경우 최대공약수는 1이며, 이런 두 수를 서로소(coprime, 互素)라고 부릅니다.