최대공약수·최소공배수 계산기 — 유클리드 호제법

직접 확인 · 2026-08 호제법 과정을 단계별로 전개해 소인수분해 방식과 결과를 대조

최대공약수와 최소공배수는 학교에서 배우고 나면 잘 안 쓸 것 같지만, 약분, 타일 배치, 주기 맞추기 같은 데서 계속 나옵니다.

결론부터

최대공약수(GCD) — 두 수를 모두 나누어떨어지게 하는 가장 큰 수
최소공배수(LCM) — 두 수의 공통 배수 중 가장 작은 수
GCD × LCM = 두 수의 곱입니다

유클리드 호제법

큰 수를 작은 수로 나눈 나머지를 반복해 구하는 방법입니다. 소인수분해보다 훨씬 빠릅니다.

24와 36의 최대공약수를 구해 봅니다.

36 ÷ 24 = 1 나머지 12
24 ÷ 12 = 2 나머지 0
→ 나머지가 0이 되기 직전의 나눈 수 12가 최대공약수

나머지가 0이 될 때까지 반복하면 됩니다. 수가 아무리 커도 몇 단계 안에 끝납니다.

최소공배수 구하기

LCM = a × b ÷ GCD

24와 36이면 24 × 36 ÷ 12 = 72입니다.

곱을 먼저 계산하면 수가 커지므로, 한쪽을 먼저 GCD로 나눈 뒤 곱하는 편이 안전합니다. 24 ÷ 12 = 2, 2 × 36 = 72입니다.

세 수 이상일 때

두 개씩 차례로 처리합니다.

GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)

12, 18, 30의 최대공약수는 GCD(12, 18) = 6, GCD(6, 30) = 6입니다.

어디에 쓰이나

약분 — 분수를 간단히 할 때 분모와 분자의 최대공약수로 나눕니다. 24/36을 12로 나누면 2/3가 됩니다.

비의 간단화 — 24 : 36을 2 : 3으로 줄이는 것도 같은 계산입니다. 비율 계산기에서 이 기능을 다룹니다.

타일과 상자 배치 — 가로 24cm, 세로 36cm 공간을 정사각형 타일로 빈틈없이 채우려면 한 변이 최대공약수인 12cm일 때 가장 큰 타일을 쓸 수 있습니다.

주기 맞추기 — 4일마다 오는 일과 6일마다 오는 일이 동시에 오는 날은 최소공배수인 12일마다입니다.

포장 단위 — 24개들이와 36개들이를 같은 수량으로 맞추려면 최소공배수 72개 단위로 주문하면 됩니다.

직접 확인해 본 것

호제법과 소인수분해를 대조해 봤습니다.

큰 수일수록 호제법이 압도적으로 빠릅니다. 1071과 462의 최대공약수를 소인수분해로 구하려면 각각 인수분해해야 하지만, 호제법으로는 세 단계면 끝납니다.

서로소인 경우 GCD가 1입니다. 공통 약수가 1뿐인 관계입니다. 이때 LCM은 두 수의 곱과 같습니다.

한 수가 다른 수의 배수면 GCD는 작은 수, LCM은 큰 수입니다. 6과 18이면 GCD 6, LCM 18입니다.

소인수분해 방식

호제법이 빠르지만, 구조를 이해하는 데는 소인수분해가 낫습니다.

24 = 2³ × 3
36 = 2² × 3²

GCD = 공통 소인수의 낮은 지수 = 2² × 3 = 12
LCM = 모든 소인수의 높은 지수 = 2³ × 3² = 72

GCD는 공통된 것만 낮은 쪽으로, LCM은 전부 높은 쪽으로 가져옵니다.

GCD × LCM = 곱

두 수에서만 성립하는 관계입니다.

GCD(a, b) × LCM(a, b) = a × b

12 × 72 = 864 = 24 × 36 ✓

세 수 이상에서는 성립하지 않습니다. 2, 3, 4의 GCD는 1, LCM은 12이지만 곱은 24입니다.

분수 계산에서

분수의 덧셈은 분모의 최소공배수로 통분합니다.

1/24 + 1/36 에서 분모의 LCM은 72이므로 3/72 + 2/72 = 5/72입니다.

분수의 약분은 분자와 분모의 GCD로 나눕니다.

이 두 가지가 분수 계산의 대부분입니다.

호제법이 왜 성립하나

"두 수의 최대공약수는 큰 수를 작은 수로 나눈 나머지와 작은 수의 최대공약수와 같다." 이 성질이 호제법의 근거입니다.

36과 24를 봅니다. 36 = 24 + 12 이므로, 36과 24를 모두 나누는 수는 12도 나눕니다. 반대로 24와 12를 모두 나누는 수는 36도 나눕니다.

즉 (36, 24)의 공약수 집합과 (24, 12)의 공약수 집합이 같습니다. 그래서 큰 수를 작은 수로 바꿔 가며 반복해도 답이 달라지지 않고, 수가 계속 작아지므로 언젠가 끝납니다.

이 방법은 기원전에 정리된 것으로 알려져 있고, 지금도 컴퓨터가 최대공약수를 구할 때 그대로 씁니다. 큰 수에서도 단계 수가 아주 적게 늘어나기 때문입니다.

생활 속 문제로 풀어 보기

색종이 자르기 — 가로 24cm, 세로 36cm 종이를 남는 부분 없이 같은 크기의 정사각형으로 자르려면 한 변이 24와 36의 공약수여야 합니다. 가장 큰 정사각형은 12cm이고, 이때 2 × 3 = 6장이 나옵니다.

버스 배차 — 한 노선은 12분마다, 다른 노선은 18분마다 옵니다. 두 노선이 동시에 오는 간격은 최소공배수인 36분입니다.

선물 나누기 — 사탕 24개와 초콜릿 36개를 남기지 않고 똑같이 나눠 줄 수 있는 최대 인원은 12명입니다. 한 명당 사탕 2개, 초콜릿 3개씩입니다.

톱니바퀴 — 톱니가 24개와 36개인 두 바퀴가 맞물려 돌 때 처음 위치로 돌아오려면 톱니 72개가 지나가야 합니다. 작은 바퀴는 3바퀴, 큰 바퀴는 2바퀴 돕니다.

프로그래밍에서

호제법은 몇 줄이면 구현됩니다.

function gcd(a, b) {
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

최소공배수는 a / gcd(a, b) * b 로 구합니다. a * b를 먼저 계산하면 자릿수가 넘칠 수 있어 나눗셈을 먼저 하는 것이 안전합니다.

이 계산기도 같은 방식으로 동작합니다.

계산기를 쓰는 방법

두 수만 필요하면 세 번째 칸을 0으로 두면 됩니다. 세 수를 넣으면 세 수 전체의 최대공약수와 최소공배수가 나옵니다.

호제법 과정도 함께 표시되므로, 과제나 시험 준비로 과정을 확인해야 할 때 그대로 옮겨 적을 수 있습니다. 첫 줄에서 작은 수가 앞에 오면 한 번 자리가 바뀌는 단계가 나오는데, 이는 알고리즘이 자동으로 큰 수와 작은 수를 정리하는 과정입니다.

가장 간단한 정수비도 함께 나옵니다. 24 : 36을 2 : 3으로 줄이는 계산이 최대공약수로 나누는 것과 같기 때문입니다.

자주 묻는 질문

Q. 0이 포함되면 어떻게 되나요? A. 0은 모든 수의 배수이므로 GCD는 다른 수 자신이 되고, LCM은 정의되지 않습니다. 이 계산기는 1 이상만 받습니다.

Q. 음수도 되나요? A. 절댓값으로 계산합니다. GCD와 LCM은 보통 양수로 정의합니다.

Q. 서로소가 뭔가요? A. 최대공약수가 1인 두 수입니다. 8과 15가 그런 예입니다.

소수와 소인수분해

최대공약수와 최소공배수의 뿌리는 소인수분해입니다.

소수는 1과 자기 자신으로만 나누어떨어지는 수입니다. 2, 3, 5, 7, 11, 13, 17, 19, 23…

모든 자연수는 소수의 곱으로 유일하게 표현됩니다. 이를 소인수분해라고 하고, 표현 방식이 하나뿐이라는 것이 산술의 기본 정리입니다.

360을 예로 들면 2³ × 3² × 5입니다. 이 표현을 알면 약수의 개수도 바로 나옵니다. 각 지수에 1을 더해 곱하면 됩니다. (3+1) × (2+1) × (1+1) = 24개입니다.

소인수분해는 수가 커지면 매우 어려워집니다. 큰 수의 소인수분해가 어렵다는 성질이 현대 암호 체계의 바탕이 되기도 합니다.

함께 보면 좋은 계산

비의 간단화는 비율 계산기에서도 할 수 있습니다.

퍼센트 변환은 퍼센트 계산기를 쓰세요.

단위 환산은 단위 변환기에서 다룹니다.

정리

유클리드 호제법은 나머지를 반복해 GCD를 구합니다
LCM = a × b ÷ GCD
타일 배치, 주기 맞추기, 약분에 쓰입니다

두 수만 있으면 되는 계산이라 손으로도 할 수 있지만, 자릿수가 커지면 호제법을 따라가는 것도 번거로워집니다.

2026년 8월 기준으로 작성했습니다.