최대공약수(GCD)·최소공배수(LCM) 완벽 가이드
최대공약수(Greatest Common Divisor, GCD)는 두 개 이상의 정수를 동시에 나누어떨어지게 하는 자연수 중 가장 큰 값을 말하며, 최소공배수(Least Common Multiple, LCM)는 두 개 이상의 정수의 공통된 배수 중 가장 작은 값을 말합니다. 초등학교 5~6학년 수학 교과 과정에서 처음 등장하지만, 중학교 이후 인수분해·분수 계산·방정식 단원은 물론 컴퓨터공학의 암호학, 자료구조 알고리즘(유클리드 호제법 기반 최적화)에서도 핵심적으로 활용되는 개념입니다.
GCD를 구하는 대표적인 방법은 두 가지입니다. 첫째, 소인수분해를 이용하는 방법으로 각 수를 소인수의 곱으로 표현한 뒤 공통으로 들어있는 소인수를 가장 작은 지수만큼 곱해주면 됩니다. 예를 들어 12 = 2²×3, 18 = 2×3² 이므로 공통 인수는 2¹×3¹ = 6이 GCD가 됩니다. 둘째, 유클리드 호제법(Euclidean Algorithm)을 이용하는 방법으로, 두 수 a, b(a≥b)에 대해 a를 b로 나눈 나머지를 r이라 할 때 gcd(a, b) = gcd(b, r)이 성립한다는 성질을 이용해 나머지가 0이 될 때까지 나눗셈을 반복합니다. 마지막으로 나머지가 0이 되었을 때의 나누는 수가 곧 최대공약수입니다. 유클리드 호제법은 소인수분해가 어려운 매우 큰 수에도 빠르게 적용할 수 있어 실무·프로그래밍에서 널리 쓰입니다.
LCM은 GCD를 알면 쉽게 구할 수 있습니다. 두 수 a, b의 최소공배수는 "a × b ÷ gcd(a, b)" 공식으로 계산되며, 세 개 이상의 수는 두 수씩 차례로 이 공식을 누적 적용합니다. 이 계산기는 큰 정수의 곱셈 과정에서 오차가 생기지 않도록 자바스크립트의 BigInt 연산을 사용해 정확한 정수 연산을 보장합니다.
두 수의 최대공약수가 1인 경우를 서로소(coprime)라고 하며, 서로소 관계는 분수의 기약분수 판별, 암호 알고리즘의 키 생성 조건 등에서 중요하게 쓰입니다. 이 도구는 입력한 여러 정수의 GCD·LCM은 물론, 소인수분해 결과에서 공통 인수를 강조 표시하고, 앞의 두 수를 기준으로 한 유클리드 호제법의 나눗셈 과정을 단계별로 보여주어 원리를 시각적으로 이해할 수 있도록 돕습니다.
자주 묻는 질문 (FAQ)
Q. 숫자를 몇 개까지 입력할 수 있나요?
A. 최소 2개부터 최대 20개까지 쉼표(,) 또는 공백으로 구분해 입력할 수 있으며, 3개 이상 입력 시 두 수씩 누적하여 전체 최대공약수와 최소공배수를 계산합니다.
Q. 음수나 0도 입력할 수 있나요?
A. 음수는 절대값을 기준으로 계산되어 부호와 무관하게 동일한 결과가 나오지만, 0은 최대공약수·최소공배수 정의상 계산에 포함할 수 없어 입력 시 오류 메시지가 표시됩니다.
Q. 유클리드 호제법 과정은 어떤 수를 기준으로 보여주나요?
A. 입력한 숫자 중 앞의 두 번째 값까지, 즉 첫 번째와 두 번째 수를 기준으로 나눗셈 반복 과정(a = b × 몫 + 나머지)을 단계별로 표시하며, 마지막 단계의 나누는 수가 두 수의 최대공약수와 일치합니다.