최대공약수(GCD)·최소공배수(LCM) 및 소인수분해 계산기

최대공약수(GCD: Greatest Common Divisor)와 최소공배수(LCM: Least Common Multiple), 그리고 소인수분해(Prime Factorization)는 기원전 300년경 유클리드의 《기하학 원론(Elements)》부터 현대 암호학(RSA, 타원곡선), 컴퓨터 알고리즘, 분산 시스템 주기에 이르기까지 정수론(Number Theory)의 기틀을 형성하는 가장 아름답고 실용적인 수학적 개념입니다. 산술의 기본정리(Fundamental Theorem of Arithmetic)에 따르면 1보다 큰 모든 자연수는 소수(Prime Number)들의 곱으로 단 한 가지 방식으로만 유일하게 분해되며, 이 소인수들은 수의 세계에서 쪼갤 수 없는 '원자(Atoms)'와 같은 역할을 수행합니다.

두 개 이상의 정수에서 공통된 약수 중 가장 큰 값을 찾는 최대공약수와 공통된 배수 중 가장 작은 값을 찾는 최소공배수는 실생활의 다양한 최적화 문제와 직결됩니다. 복잡한 분수의 약분과 통분은 물론, 서로 다른 크기의 직사각형 공간을 남김없이 채울 수 있는 최대 크기의 정사각형 타일을 재단하거나, 톱니 수가 다른 여러 기어들이 처음 맞물렸던 위치로 다시 되돌아오는 최소 회전 주기를 산출하는 데 필수적입니다. 두 양의 정수 $a, b$에 대하여 $a \times b = \text{GCD}(a, b) \times \text{LCM}(a, b)$라는 대칭적 항등식은 정수론의 가장 우아한 결실 중 하나입니다.

특히 유클리드 호제법(Euclidean Algorithm)은 인류 역사상 가장 오래되었으면서도 현대 컴퓨터 과학에서 가장 효율적인 알고리즘으로 손꼽힙니다. 아무리 큰 천문학적 숫자라도 나눗셈의 나머지를 반복해서 취하는 로그 시간 복잡도($O(\log(\min(a, b)))$)로 순식간에 최대공약수를 도출합니다. 오르보킷 GCD·LCM·소인수분해 계산기는 2개 이상의 정수를 입력받아 유클리드 호제법 기반의 GCD·LCM 계산, 각 숫자의 소인수 거듭제곱 분해식, 모든 양의 약수 목록 및 개수·합계까지 단계별 풀이와 함께 완벽히 제공합니다.