최대공약수 · 최소공배수 계산기

최종 업데이트: 2026-05-13

두 정수 사이의 두 가지 기본 관계

양의 정수 두 개로 이루어진 쌍에는 항상 두 가지 특별한 수가 존재합니다. 하나는 두 수를 모두 나누어 떨어지게 하는 가장 큰 양의 정수(최대공약수, GCD)이고, 다른 하나는 두 수의 공통 배수 중 가장 작은 양의 정수(최소공배수, LCM)입니다.

이 두 수는 두 정수 사이의 산술적 관계를 간결하게 나타냅니다.

12와 8을 예로 들겠습니다.

• 12와 8의 공약수는 1, 2, 4입니다. 그 중 가장 큰 것은 4입니다.
• 12와 8의 공배수는 24, 48, 72, …입니다. 그 중 가장 작은 것은 24입니다.

유클리드 호제법으로 최대공약수 구하기

최대공약수를 구하는 가장 오래된 — 그리고 실용적으로도 여전히 가장 빠른 — 방법은 유클리드 호제법입니다. 기원전 300년경 유클리드의 『원론』에 기술된 방법으로, 핵심 원리는 다음과 같습니다.

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

여기서 $a \bmod b$는 $a$를 $b$로 나눈 나머지입니다. 나머지가 0이 될 때까지 반복하며, 마지막으로 등장한 0이 아닌 나머지가 최대공약수가 됩니다.

예: GCD(48, 18)

단계	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0

마지막 0이 아닌 나머지는 6이므로, GCD(48, 18) = 6입니다.

이 알고리즘은 놀라울 만큼 효율적입니다. 단계 수는 더 작은 수의 자릿수의 다섯 배를 절대 넘지 않습니다.

최대공약수와 최소공배수의 등식

최대공약수를 구하고 나면 최소공배수는 단 하나의 공식으로 구할 수 있습니다.

$\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

이는 우연이 아니라 정수의 소인수분해 유일성 정리에서 도출되는 정리입니다. 각 정수를 소수의 거듭제곱의 곱으로 나타내면, 최대공약수는 각 소수의 지수 중 최솟값을 취하고 최소공배수는 최댓값을 취합니다. 두 값의 곱은 항상 $a \times b$가 됩니다.

예: LCM(12, 8)

$\text{GCD}(12, 8) = 4, \quad \text{LCM}(12, 8) = \frac{12 \times 8}{4} = 24$

확인: $4 \times 24 = 96 = 12 \times 8$. ✓

이 두 수가 중요한 이유

분수 약분

$\dfrac{a}{b}$를 기약분수로 만들려면 분자와 분모를 $\gcd(a, b)$로 나눕니다. 예를 들어 $\gcd(12, 8) = 4$이므로 $\dfrac{12}{8}$는 $\dfrac{3}{2}$로 약분됩니다.

분수 덧셈

$\dfrac{1}{12} + \dfrac{1}{8}$을 계산하려면 최소공통분모가 필요하며, 이것이 바로 $\text{LCM}(12, 8) = 24$입니다.

$\frac{1}{12} + \frac{1}{8} = \frac{2}{24} + \frac{3}{24} = \frac{5}{24}$

주기와 사이클

두 사건이 각각 $a$일, $b$일마다 반복된다면 다음번 동시 발생은 $\text{LCM}(a, b)$일 후입니다. 톱니바퀴 치수비, 타일 패턴의 주기, 역법 문제(두 천문 주기가 다시 일치하는 때는?) 등에 최소공배수가 등장하는 이유입니다.

암호학

유클리드 알고리즘은 RSA 암호화의 핵심 연산으로, 선택한 키 지수가 모듈러스의 오일러 함수와 서로소인지 검증하는 데 최대공약수가 사용됩니다.

특수한 경우

• GCD(a, 0) = a (임의의 양의 정수 $a$): 유클리드 알고리즘의 기저 조건으로, 정의에서 자연스럽게 도출됩니다.
• 서로소인 수: 최대공약수 = 1이고 최소공배수 = a × b입니다. 예를 들어 GCD(7, 13) = 1, LCM(7, 13) = 91.
• 같은 수: GCD(n, n) = n이고 LCM(n, n) = n입니다.

빠른 참고표

성질	공식
유클리드 호제법	$\gcd(a, b) = \gcd(b,\ a \bmod b)$
최대공약수로 최소공배수 구하기	$\text{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$
등식	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$
분수 약분	분자와 분모를 $\gcd$로 나눔
공통분모	두 분모의 $\text{lcm}$ 사용

자주 묻는 질문 (FAQ)

최대공약수란 무엇입니까?

최대공약수(GCD)는 두 정수를 모두 나누어 떨어지게 하는 가장 큰 양의 정수입니다. 예를 들어 GCD(12, 8) = 4인데, 4가 12와 8을 모두 나머지 없이 나눌 수 있는 가장 큰 수이기 때문입니다.

최소공배수란 무엇입니까?

최소공배수(LCM)는 두 정수의 공통 배수 중 가장 작은 양의 정수입니다. 예를 들어 LCM(12, 8) = 24인데, 24가 12와 8 모두의 배수 중 가장 작은 수이기 때문입니다.

최대공약수와 최소공배수는 어떤 관계입니까?

임의의 두 양의 정수 a와 b에 대해 GCD(a, b) × LCM(a, b) = a × b가 성립합니다. 따라서 하나를 알면 다른 하나를 구할 수 있습니다(LCM = a × b ÷ GCD). 이 관계 때문에 두 값을 함께 계산하는 경우가 많습니다.