최대공약수・최소공배수 계산기
두 개의 양의 정수를 입력하면 유클리드 호제법으로 최대공약수（GCD）를 구하고, 그 계산 과정을 단계별로 표시합니다. 최소공배수（LCM）도 동시에 산출합니다.
| 최대공약수（GCD） | |
|---|---|
| 최소공배수（LCM） |
유클리드 호제법 계산 과정
| 계산식 |
|---|
| = × + |
유클리드 호제법이란
유클리드 호제법은 두 정수의 최대공약수를 구하는 고전적인 알고리즘입니다. "큰 수를 작은 수로 나눈 나머지에 주목하고, 나누는 수와 나머지의 조합으로 같은 연산을 반복한다. 나머지가 0이 되었을 때의 나누는 수가 최대공약수이다"라는 절차로, 아무리 큰 수라도 적은 단계로 정확하게 최대공약수를 구할 수 있습니다. 기원전 300년경 유클리드의 저서 『원론』에 기록된, 현존하는 가장 오래된 알고리즘 중 하나로도 알려져 있습니다.
최대공약수·최소공배수 계산이란
최대공약수(GCD)는 두 정수를 공통으로 나누어떨어지게 하는 가장 큰 정수이고, 최소공배수(LCM)는 두 정수의 공통 배수 가운데 가장 작은 정수입니다. 본 도구는 두 양의 정수를 입력하기만 하면 이 두 값을 유클리드 호제법으로 즉시 산출하고, 도중의 계산 과정(피제수·제수·몫·나머지)도 단계마다 표시합니다.
손계산으로는 소인수분해에서 공통 인수를 찾는 방법이 일반적이지만, 수가 커질수록 소인수분해 자체에 품이 듭니다. 본 도구가 채택한 유클리드 호제법은 나눗셈의 반복만으로 최대공약수를 구할 수 있으므로, 자릿수가 큰 정수끼리도 같은 절차로 계산할 수 있습니다. 입력은 1 이상의 정수로 한정되며, 0·음수·소수를 입력한 경우에는 계산 결과를 표시하지 않습니다.
최대공약수·최소공배수 계산 사용법
- 수치 A를 입력합니다 최대공약수·최소공배수를 구하고자 하는 첫 번째 양의 정수를 입력합니다.
- 수치 B를 입력합니다 또 하나의 양의 정수를 입력합니다. A와 B의 크고 작음은 어느 쪽이 먼저여도 결과가 달라지지 않습니다.
- 결과를 확인합니다 최대공약수(GCD)와 최소공배수(LCM)가 자동으로 표시됩니다.
- 계산 과정을 확인합니다 유클리드 호제법의 각 단계(피제수＝제수×몫＋나머지)가 표로 표시되므로, 나머지가 0이 될 때까지의 절차를 따라갈 수 있습니다.
더 잘 활용하기 위한 팁
- 최소공배수（LCM）는 "A×B÷최대공약수（GCD）"라는 공식으로 구할 수 있습니다. 분수의 통분이나, 주기가 다른 여러 일정이 겹치는 시점을 구할 때 자주 사용됩니다.
- 두 수가 서로소（최대공약수가 1）인 경우, 최소공배수는 단순히 A×B와 일치합니다.
- 유클리드 호제법은 큰 수끼리의 최대공약수를 구할 때도 소인수분해를 거치는 것보다 빠르게 계산할 수 있다는 실용적인 장점이 있습니다.
- 입력하는 두 수의 크기 순서는 결과에 영향을 주지 않습니다. 내부적으로 자동으로 큰 수부터 계산을 시작합니다.
최대공약수·최소공배수 계산의 활용 상황
분수 약분의 사전 준비
분자와 분모의 최대공약수를 구하면, 그 수로 양쪽을 나누어 분수를 약분할 수 있습니다. 실제로 약분한 결과까지 확인하고 싶다면 약분 기능이 있는 분수 계산기가 편리합니다.
여러 주기가 겹치는 시점의 계산
예컨대 3일 간격과 5일 간격으로 생기는 일정이 다음에 같은 날에 겹치는 것은 3과 5의 최소공배수인 15일 뒤입니다. 근무조나 행사의 주기 조정에 응용할 수 있습니다.
수학 숙제·시험 대비의 검산
손으로 구한 최대공약수·최소공배수가 맞는지, 계산 과정까지 포함해 바로 검산할 수 있습니다.
통분의 분모를 구하는 준비
서로 다른 분모를 가진 여러 분수를 통분할 때, 각 분모의 최소공배수가 새로운 공통 분모가 됩니다.
암호 기술의 기초 지식 확인
RSA 암호의 키 생성 등, 최대공약수의 계산은 현대 암호 기술의 바탕에도 쓰이고 있어, 구조를 이해하는 첫걸음으로 계산 과정을 확인하는 데 도움이 됩니다.
용어집
- 최대공약수(GCD)
- 둘 이상의 정수를 모두 나누어떨어지게 하는 정수(공약수) 가운데 가장 큰 것입니다. 영어로는 Greatest Common Divisor라 하며 GCD로 줄여 씁니다.
- 최소공배수(LCM)
- 둘 이상의 정수의 공통 배수(공배수) 가운데 가장 작은 것입니다. 영어로는 Least Common Multiple이라 하며 LCM으로 줄여 씁니다.
- 유클리드 호제법
- 큰 수를 작은 수로 나눈 나머지에 주목하여, 나누는 수와 나머지의 짝으로 같은 조작을 되풀이해 최대공약수를 구하는 알고리즘입니다. 고대 그리스 수학자 유클리드의 저서에서 유래합니다.
- 서로소
- 두 정수의 최대공약수가 1임을 가리킵니다. 서로소인 두 수의 최소공배수는 단순히 그 두 수를 곱한 값이 됩니다.
- 소인수분해
- 정수를 소수의 곱의 꼴로 분해하는 것입니다. 최대공약수·최소공배수는 공통되는 소인수의 조합에서 구할 수도 있지만, 수가 클 경우에는 유클리드 호제법 쪽이 빠릅니다.
- 공약수·공배수
- 공약수는 여러 정수에 공통되는 약수, 공배수는 여러 정수에 공통되는 배수를 말합니다. 최대공약수·최소공배수는 각각 그 가운데 가장 크거나 작은 것을 가리킵니다.
자주 묻는 질문
여담 ― 2000년도 더 된 알고리즘이 지금도 현역인 이유
유클리드 호제법은 기원전 300년경 고대 그리스 수학자 유클리드가 저술한 수학책 『원론』（Elements） 제7권에 기록된 방법입니다. 현존하는 기록 중 가장 오래된 알고리즘 중 하나로 여겨지며, 2000년이 넘게 지난 오늘날에도 컴퓨터 과학 교과서에서 가장 먼저 소개되는 대표적인 알고리즘으로 남아 있습니다.
이 알고리즘이 오랫동안 계속 사용되는 이유는 그 계산 효율의 높음에 있습니다. 수학적으로, 유클리드 호제법이 필요로 하는 단계 수는 입력하는 수의 자릿수에 비례하는 정도에 그친다는 것이 증명되어 있어（최악의 경우는 피보나치 수열과 관련된 수의 조합에서 발생합니다）, 아무리 큰 정수끼리라도 현실적인 시간 안에 최대공약수를 계산할 수 있습니다.
현대 암호 기술（RSA 암호 등）에서도 키 생성 과정에서 최대공약수 계산（또는 그 확장판인 확장 유클리드 호제법）이 사용되고 있으며, 고대의 수학적 발견이 오늘날 인터넷 보안을 떠받치는 기반 기술의 일부가 되었다는 점은 수학의 보편성을 보여주는 흥미로운 사실입니다.