최대공약수·최소공배수 구하는 법
유클리드 호제법은 큰 수를 작은 수로 나눈 나머지로 계속 바꿔가며 문제를 점점 더 작은 수의 문제로 줄여 나갑니다. 나머지가 0이 되는 그 나눗셈에서 나눗수로 쓴 수가 최대공약수입니다. 최소공배수는 이렇게 구한 최대공약수로부터 곱셈과 나눗셈 한 번으로 바로 얻어집니다.
- a, b — 입력한 두 수. 순서를 바꿔 넣어도 결과는 같습니다
- GCD — a와 b를 나머지 없이 모두 나누는 수 중 가장 큰 수(최대공약수)
- LCM — a의 배수이면서 동시에 b의 배수이기도 한 수 중 가장 작은 수(최소공배수)
- n — 소수인지 판별하거나 소인수분해할 자연수
- pᵢ, eᵢ — i번째 소인수와 그 소인수가 n을 나누는 횟수(지수)
자세한 설명
유클리드 호제법의 원리
두 수 a, b(a가 더 큼)의 최대공약수를 구할 때, a를 b로 나눈 나머지를 r이라 하면 GCD(a, b) = GCD(b, r)이 항상 성립합니다. a와 b를 동시에 나누는 수는 b와 r도 똑같이 나누기 때문입니다(a = b×몫 + r이므로, b와 r을 나누는 수는 a도 나눕니다). 그래서 나머지가 0이 될 때까지 '큰 수를 작은 수로 나눈 나머지로 바꾸는' 과정을 반복해도 최대공약수는 전혀 변하지 않고, 나머지가 0이 되는 순간의 나눗수가 곧 답입니다.
계산 과정: 48과 180의 최대공약수·최소공배수
실제 계산 과정을 그대로 따라가 보면, 180 = 48×3 + 36(180에서 48을 세 번 빼면 36이 남음), 48 = 36×1 + 12(48에서 36을 한 번 빼면 12가 남음), 36 = 12×3 + 0(36은 12로 나누어떨어짐)입니다. 나머지가 0이 된 순간의 나눗수인 12가 48과 180의 최대공약수입니다. 최소공배수는 LCM = a×b÷GCD = 48×180÷12 = 8640÷12 = 720으로 바로 구해지고, 검산하면 12×720 = 8640으로 48×180과 정확히 같습니다.
근거: 최대공약수 × 최소공배수 = 두 수의 곱인 이유
근거: 이 항등식은 소인수분해로 설명할 수 있습니다. 48 = 2⁴×3¹, 180 = 2²×3²×5¹로 소인수분해되는데, 최대공약수는 공통으로 들어있는 소인수를 낮은 지수만큼만 취해서 2²×3¹ = 4×3 = 12이고, 최소공배수는 반대로 각 소인수를 높은 지수만큼 취해서 2⁴×3²×5¹ = 16×9×5 = 720입니다. 어느 소인수든 최대공약수 쪽 지수(작은 값)와 최소공배수 쪽 지수(큰 값)를 더하면 원래 두 수의 지수를 각각 더한 것과 같아지므로, 최대공약수와 최소공배수를 곱하면 항상 원래 두 수를 곱한 값과 같아집니다.
소인수분해로 구하는 법과 유클리드 호제법, 무엇이 다를까
학교에서는 두 수를 각각 소인수분해한 뒤 공통 소인수를 골라 최대공약수를, 모든 소인수를 모아 최소공배수를 구하는 방법을 먼저 배웁니다. 원리를 눈으로 확인하기에는 이 방법이 좋지만, 수가 커질수록 소인수분해 자체가 점점 어려워집니다. 반면 유클리드 호제법은 수가 커져도 나눗셈 횟수가 자릿수에 비례해 느는 정도라(나머지가 매번 크게 줄어듭니다), 자릿수가 많은 두 수의 최대공약수도 아주 빠르게 구할 수 있습니다. 그래서 계산기나 프로그램은 대부분 유클리드 호제법을 사용합니다. 두 방법 모두 정답은 똑같이 나오므로, 손으로 원리를 익힐 때는 소인수분해로 검산해 보고 실제 계산은 호제법으로 빠르게 처리하는 방식도 좋은 공부법입니다.
실생활에서 최대공약수·최소공배수가 쓰이는 곳
가로 48cm, 세로 180cm인 벽면을 자르지 않고 정사각형 타일로 채우려면 타일 한 변의 최대 길이는 GCD(48,180) = 12cm이고, 가로 4장·세로 15장으로 딱 60장이 필요합니다(약분에도 같은 원리가 쓰여 48/180은 GCD 12로 나누면 4/15가 됩니다). 12분 간격과 18분 간격으로 출발하는 두 버스가 다시 동시에 출발하는 시각은 LCM(12,18) = 36분 뒤이고, 이가 8개인 톱니바퀴와 12개인 톱니바퀴가 처음 위치로 함께 돌아오려면 LCM(8,12) = 24만큼 이가 맞물려야 하므로 작은 톱니바퀴는 3바퀴, 큰 톱니바퀴는 2바퀴를 돕니다. 분모가 다른 분수 1/12와 1/18을 더할 때도 공통분모로 LCM(12,18) = 36을 써서 3/36 + 2/36 = 5/36으로 계산합니다.
서로소(coprime)와 이 페이지의 기준일
두 수가 1 외에는 공약수를 갖지 않으면 서로소라 부르며, 이때 최대공약수는 항상 1이고 최소공배수는 두 수를 그냥 곱한 값과 같습니다. 예를 들어 7과 5는 7 = 5×1 + 2, 5 = 2×2 + 1, 2 = 1×2 + 0으로 최대공약수가 1이 되어 서로소이고, 최소공배수는 7×5 = 35입니다. 반대로 1 이상인 두 수가 서로소가 아니라면 최소공배수는 항상 두 수의 곱보다 작아지며(A나 B가 0이면 최소공배수도 곱도 0이라 이 비교가 성립하지 않습니다), 정확히는 두 수의 곱을 최대공약수로 나눈 값입니다. 최대공약수·최소공배수를 구하는 수학적 원리 자체는 시대와 무관하게 변하지 않지만, 이 페이지의 예시와 설명 문구는 2026년을 기준일로 삼아 마지막으로 다듬었습니다.
소수 판별 · 소인수분해 탭
「소수 판별」 탭은 1부터 √n까지의 정수로 차례로 나눠 보고 약수를 모두 모읍니다. 17은 약수가 1과 17 두 개뿐이라 소수, 12는 1, 2, 3, 4, 6, 12 여섯 개라 합성수입니다. 「소인수분해」 탭은 2부터 나누어떨어지는 만큼 나눠 나갑니다. 60 → 30 → 15(2로 두 번), 15 → 5(3으로 한 번), 남은 5는 소수이므로 60 = 2² × 3 × 5이고 서로 다른 소인수는 3개입니다.
활용 팁. 분수를 기약분수로 만들 때는 분자·분모를 GCD로 나누면 되고(48/180 → 4/15), 분모가 다른 분수를 더하거나 뺄 때는 공통분모로 LCM을 씁니다. 주기가 다른 두 사건이 다시 겹치는 시점(버스 출발, 톱니바퀴가 같은 위치로 돌아오는 순간)을 구할 때도 LCM이 그대로 쓰입니다. 숫자가 커서 소인수분해가 번거롭다면 위 계산기에 값을 넣어 유클리드 호제법 결과를 바로 확인하는 편이 훨씬 빠릅니다.
자주 묻는 질문
48과 180의 최대공약수와 최소공배수는 얼마인가요?
계산 과정은 180 = 48×3+36 → 48 = 36×1+12 → 36 = 12×3+0으로, 최대공약수는 12입니다. 최소공배수는 48×180÷12 = 720이며, 12×720 = 8640 = 48×180으로 검산됩니다. 위 입력창에 원하는 두 수를 넣으면 같은 방식으로 즉시 계산됩니다.
최대공약수와 최소공배수는 어떤 관계가 있나요?
근거: 임의의 두 양의 정수 a, b에 대해 GCD(a,b) × LCM(a,b) = a × b가 항상 성립합니다. 소인수분해로 보면 각 소인수마다 최대공약수는 작은 지수를, 최소공배수는 큰 지수를 가져가므로 둘을 곱하면 원래 두 수의 지수 합과 같아지기 때문입니다. 이 계산기도 호제법으로 구한 최대공약수에 이 관계식을 적용해 최소공배수를 얻습니다.
1은 소수인가요? 17은요?
1은 소수가 아닙니다. 소수는 약수가 정확히 2개여야 하는데 1은 약수가 1 하나뿐이라, 관례상 소수도 합성수도 아닙니다. 17은 약수가 1과 17뿐이라 소수입니다. 「소수 판별」 탭에 넣으면 약수 목록과 개수가 함께 나옵니다.
60의 소인수분해는 어떻게 되나요?
60 = 2² × 3 × 5입니다. 2로 두 번 나누고(60 → 30 → 15), 3으로 한 번 나누면(15 → 5) 소수 5가 남습니다. 서로 다른 소인수는 2, 3, 5 세 개입니다. 「소인수분해」 탭에서 바로 확인할 수 있습니다.
서로소란 무엇이고, 분수의 약분·통분에 최대공약수·최소공배수를 어떻게 쓰나요?
서로소는 1 외에 공약수가 없는 두 수를 말하며(예: 7과 5, GCD 1, LCM 35), 이때 최소공배수는 두 수의 곱과 같습니다. 분수를 약분할 때는 분자·분모를 GCD로 나누고(48/180 → GCD 12로 나눠 4/15), 분모가 다른 분수를 더하거나 뺄 때는 두 분모의 LCM을 공통분모로 씁니다(1/12+1/18은 LCM 36을 써서 3/36+2/36=5/36).