작동 방식
최대공약수(GCD)는 유클리드 호제법으로 구해요. 큰 수를 작은 수로 나눈 나머지로 바꾸는 일을 나머지가 0이 될 때까지 반복해요. 세 수 이상이면 두 수씩 차례로 계산해요.
최소공배수(LCM)는 최대공약수에서 나와요: lcm(a, b) = |a × b| ÷ gcd(a, b)를 두 수씩 적용해요. 모든 계산을 정확한 정수로 해서 30자리 수도 오차 없이 나와요.
유클리드 호제법 단계별 풀이
1071과 462의 예: 각 줄에서 앞의 나누는 수를 나머지로 나누고, 마지막으로 0이 아닌 나머지가 최대공약수예요.
- 1071 = 2 × 462 + 147
- 462 = 3 × 147 + 21
- 147 = 7 × 21 + 0 → gcd = 21
gcd(a, b) = gcd(b, a mod b) · lcm(a, b) = |a × b| ÷ gcd(a, b)
이럴 때 써요
- 최대공약수: 분수 약분. 18/24를 최대공약수 6으로 나누면 3/4.
- 최소공배수: 통분하거나, 주기가 다른 일이 다시 겹치는 때 찾기(4일마다·6일마다 → 12일마다).
- 최대공약수: 타일·줄·모둠을 남김없이 같은 크기로 나누기.
팁
- 최대공약수가 1이면 서로소예요. 8과 9처럼 둘 다 합성수여도 서로소일 수 있어요.
- 양의 정수 두 개는 gcd(a, b) × lcm(a, b) = a × b라서 검산에 편해요.
- 0도 넣을 수 있어요. gcd(a, 0) = a이고, 0이 포함된 최소공배수는 0이에요.
기준과 출처
최종 검토 2026년 10월 20일
자주 묻는 질문
최대공약수와 최소공배수는 어떻게 다른가요?
최대공약수는 모든 수를 나누어떨어지게 하는 가장 큰 수이고, 최소공배수는 모든 수로 나누어떨어지는 가장 작은 수예요. 12와 18이면 최대공약수 6, 최소공배수 36이에요.
GCD, GCF, HCF는 같은 건가요?
네. 모두 최대공약수를 가리키는 영어 이름이에요.
숫자를 몇 개까지 넣을 수 있나요?
개수 제한은 없고 두 수씩 차례로 계산해요. 소인수분해는 처음 12개 수까지 보여 드려요.