유클리드 호제법이란?
유클리드 호제법은 가장 오래된 알고리즘 중 하나로, 기원전 300년경 그리스 수학자 유클리드가 정리한 방법입니다. 두 정수의 최대공약수(GCD), 즉 두 수를 나머지 없이 나누는 가장 큰 수를 효율적으로 찾아냅니다. 이 계산기는 최대공약수에서 바로 도출되는 최소공배수(LCM)도 함께 알려줍니다.
계산기 사용 방법
위 입력란에 정수 두 개를 넣고 실행하세요. 계산기는 입력값의 절댓값을 사용하며, \(\gcd(a, b) = \gcd(b, a \bmod b)\) 규칙을 나머지가 0이 될 때까지 반복 적용합니다. 그런 다음 최대공약수와 최소공배수를 모두 보여줍니다.
공식 풀이
핵심 원리는 이렇습니다. 큰 수를 작은 수로 나눈 나머지로 큰 수를 대체해도 두 수의 최대공약수는 변하지 않는다는 것입니다. 수식으로는 $$\gcd(a, b) = \gcd(b, a \bmod b)$$이며, b가 0이 될 때까지 이 과정을 반복합니다. 이때 마지막으로 남은 0이 아닌 값이 바로 최대공약수입니다. 최소공배수는 $$\operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$$로 구합니다. 두 수의 곱은 곧 두 수의 최대공약수와 최소공배수의 곱과 같기 때문입니다.
예제로 알아보기
\(\gcd(48, 36)\)을 구해 봅시다. \(48 \bmod 36 = 12\)이므로 \(\gcd(36, 12)\)가 됩니다. 이어서 \(36 \bmod 12 = 0\)이므로 최대공약수는 12입니다. 최소공배수는 $$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$가 됩니다.
자주 묻는 질문
한 수가 0이면 어떻게 되나요? \(\gcd(a, 0) = a\)입니다. 알고리즘이 이를 자연스럽게 처리하여 반복이 즉시 멈추고 0이 아닌 값을 반환합니다.
a와 b의 순서가 중요한가요? 아니요. \(\gcd(a, b) = \gcd(b, a)\)이며, 알고리즘이 첫 단계에서 자동으로 순서를 바로잡습니다.
음수를 입력해도 되나요? 됩니다. 최대공약수는 관례적으로 양수로 정의되므로, 계산기는 절댓값을 사용합니다.
