최대공약수란?
두 정수의 최대공약수(GCD, Greatest Common Divisor)는 두 수를 모두 나누어떨어지게 하는 가장 큰 양의 정수를 말합니다. 영어권에서는 HCF(Highest Common Factor)라고도 부르는데, 둘은 완전히 같은 개념입니다. 예를 들어 48과 36의 최대공약수는 12입니다. 12가 두 수를 모두 나누어떨어지게 하는 가장 큰 수이기 때문이죠. 이 계산기는 그 값을 즉시 찾아 주고, 최소공배수(LCM)까지 함께 알려 줍니다.
계산기 사용 방법
A와 B 칸에 두 개의 정수를 입력한 뒤 결과를 확인하면 됩니다. 입력값은 절댓값으로 처리되므로 음수를 넣어도 올바르게 계산됩니다. 한쪽에 0을 입력하면, 모든 정수는 0을 나누므로 최대공약수는 나머지 한 수와 같아집니다.
유클리드 호제법 원리
이 계산기는 지금까지도 널리 쓰이는 가장 오래된 알고리즘 중 하나인 유클리드 호제법을 사용합니다. 핵심은 다음의 간단한 성질입니다: \(\gcd\left(a,\ b\right) = \gcd\left(b,\ a \bmod b\right)\). 두 수를 나눈 나머지로 큰 수를 계속 바꿔 나가다가 나머지가 0이 되면 멈추고, 마지막으로 0이 아니었던 나누는 수가 바로 최대공약수입니다. 이 방법은 소인수분해를 하지 않아도 되기 때문에 아주 큰 수에서도 매우 빠르게 동작합니다.
풀이 예시
gcd(48, 36)을 구해 봅시다:
$$48 \bmod 36 = 12 \rightarrow \gcd\left(36,\ 12\right)$$
$$36 \bmod 12 = 0 \rightarrow \gcd\left(12,\ 0\right) = \mathbf{12}$$
이때 최소공배수는 $$\text{lcm} = \frac{\left|48 \times 36\right|}{12} = \frac{1728}{12} = \mathbf{144}$$ 입니다.
자주 묻는 질문
GCD와 HCF는 어떻게 다른가요? 차이가 없습니다. 같은 값을 가리키는 두 가지 이름일 뿐입니다. "Greatest Common Divisor(최대공약수)"는 미국에서, "Highest Common Factor"는 영국에서 주로 쓰입니다.
서로소인 두 수의 최대공약수는 무엇인가요? 항상 1입니다. 8과 15처럼 1 외에는 공약수가 없는 두 수를 서로소(coprime) 또는 상대적으로 소수인 관계라고 합니다.
최대공약수가 작은 수보다 클 수 있나요? 아니요. 최대공약수는 두 입력값 중 작은 수를 절대 넘을 수 없습니다. 작은 수가 큰 수를 나누어떨어지게 할 때, 최대공약수는 바로 그 작은 수와 같아집니다.
