유클리드 호제법(최대공약수) 계산기

계산 입력

첫 번째 수 (a)

두 번째 수 (b)

공식

Show calculation steps (1)

1. LCM (from GCD)

   

   LCM is derived as the product of a and b divided by their GCD.

결과

최대공약수

12

gcd(48, 36)

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

유클리드 호제법이란?

유클리드 호제법은 가장 오래된 알고리즘 중 하나로, 기원전 300년경 그리스 수학자 유클리드가 정리한 방법입니다. 두 정수의 최대공약수(GCD), 즉 두 수를 모두 나누어떨어지게 하는 가장 큰 수를 찾아 줍니다. 이 계산기는 음이 아닌 두 정수에 알고리즘을 적용하며, 최소공배수(LCM)까지 함께 알려 드립니다.

사용 방법

a와 b 입력란에 두 수를 넣고 실행하세요. 최대공약수(GCD)가 메인 결과로, 최소공배수(LCM)가 보조 결과로 표시됩니다. 순서는 상관없습니다 — \(\gcd(48, 36)\)과 \(\gcd(36, 48)\)은 동일합니다. 음수를 입력하면 절댓값으로 처리되며, 한 수가 0이면 GCD는 다른 수가 됩니다.

공식 풀이

이 알고리즘은 간단한 통찰에서 출발합니다. a와 b의 공약수는 그 나머지인 a mod b도 나누어떨어지게 한다는 점입니다. 그래서 더 큰 수를 나머지로 계속 바꿔 나갑니다.

$$\gcd(a, b) = \gcd(b,\, a \bmod b)$$ 그리고 기저 조건은 $$\gcd(a, 0) = a$$ 입니다.

매 단계마다 수가 빠르게 줄어들기 때문에, 아주 큰 값이라도 몇 번의 반복만으로 답이 나옵니다. LCM은 $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$ 로 계산합니다.

각 단계는 나머지가 0이 될 때까지 (a, b)를 (b, a mod b)로 바꿉니다.

예제 풀이

\(\gcd(48, 36)\)을 구해 봅시다.

$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$ $$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$

따라서 GCD는 12이고, $$\operatorname{lcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$ 입니다.

기하학적으로 최대공약수는 a×b 직사각형을 채우는 가장 큰 정사각형의 변입니다.

자주 묻는 질문

두 수가 모두 0이면 어떻게 되나요? 여기서는 0과 0의 GCD를 0으로 정의합니다. 양의 배수가 존재하지 않으므로 LCM도 0입니다.

약수를 일일이 나열하는 것보다 왜 빠른가요? 모든 약수를 찾는 대신 나머지를 이용한 지름길을 쓰기 때문입니다. 매 단계마다 문제 크기가 크게 줄어들어 보통 로그 시간(logarithmic time)에 해결됩니다.

아주 큰 수도 처리할 수 있나요? 가능합니다. 유클리드 호제법은 자릿수가 많은 수에도 효율적이며, 적은 횟수의 나머지 연산만으로 답을 구합니다.