최대공약수・최소공배수 계산기
두 개의 양의 정수를 입력하면 유클리드 호제법으로 최대공약수（GCD）를 구하고, 그 계산 과정을 단계별로 표시합니다. 최소공배수（LCM）도 동시에 산출합니다.
| 최대공약수（GCD） | |
|---|---|
| 최소공배수（LCM） |
유클리드 호제법 계산 과정
| 계산식 |
|---|
| = × + |
유클리드 호제법이란
유클리드 호제법은 두 정수의 최대공약수를 구하는 고전적인 알고리즘입니다. "큰 수를 작은 수로 나눈 나머지에 주목하고, 나누는 수와 나머지의 조합으로 같은 연산을 반복한다. 나머지가 0이 되었을 때의 나누는 수가 최대공약수이다"라는 절차로, 아무리 큰 수라도 적은 단계로 정확하게 최대공약수를 구할 수 있습니다. 기원전 300년경 유클리드의 저서 『원론』에 기록된, 현존하는 가장 오래된 알고리즘 중 하나로도 알려져 있습니다.
팁
- 최소공배수（LCM）는 "A×B÷최대공약수（GCD）"라는 공식으로 구할 수 있습니다. 분수의 통분이나, 주기가 다른 여러 일정이 겹치는 시점을 구할 때 자주 사용됩니다.
- 두 수가 서로소（최대공약수가 1）인 경우, 최소공배수는 단순히 A×B와 일치합니다.
- 유클리드 호제법은 큰 수끼리의 최대공약수를 구할 때도 소인수분해를 거치는 것보다 빠르게 계산할 수 있다는 실용적인 장점이 있습니다.
- 입력하는 두 수의 크기 순서는 결과에 영향을 주지 않습니다. 내부적으로 자동으로 큰 수부터 계산을 시작합니다.
자주 묻는 질문
여담 ― 2000년도 더 된 알고리즘이 지금도 현역인 이유
유클리드 호제법은 기원전 300년경 고대 그리스 수학자 유클리드가 저술한 수학책 『원론』（Elements） 제7권에 기록된 방법입니다. 현존하는 기록 중 가장 오래된 알고리즘 중 하나로 여겨지며, 2000년이 넘게 지난 오늘날에도 컴퓨터 과학 교과서에서 가장 먼저 소개되는 대표적인 알고리즘으로 남아 있습니다.
이 알고리즘이 오랫동안 계속 사용되는 이유는 그 계산 효율의 높음에 있습니다. 수학적으로, 유클리드 호제법이 필요로 하는 단계 수는 입력하는 수의 자릿수에 비례하는 정도에 그친다는 것이 증명되어 있어（최악의 경우는 피보나치 수열과 관련된 수의 조합에서 발생합니다）, 아무리 큰 정수끼리라도 현실적인 시간 안에 최대공약수를 계산할 수 있습니다.
현대 암호 기술（RSA 암호 등）에서도 키 생성 과정에서 최대공약수 계산（또는 그 확장판인 확장 유클리드 호제법）이 사용되고 있으며, 고대의 수학적 발견이 오늘날 인터넷 보안을 떠받치는 기반 기술의 일부가 되었다는 점은 수학의 보편성을 보여주는 흥미로운 사실입니다.