최대공약수(GCD)와 최소공배수(LCM)란?
최대공약수(GCD)는 두 개 이상의 정수를 모두 나누어떨어지게 하는 약수 가운데 가장 큰 수이고,최소공배수(LCM)는 그 수들의 공통 배수 가운데 가장 작은 양의 정수입니다. 분수를 약분할 때는 분자와 분모의 최대공약수로 나누고, 분모가 다른 분수를 더할 때는 분모들의 최소공배수로 통분합니다. 또 12분 간격과 18분 간격으로 출발하는 두 버스가 다음에 동시에 출발하는 시각, 가로 84cm·세로 126cm 바닥을 틈 없이 정사각형 타일로 덮을 때 가장 큰 타일 한 변처럼 "언제 다시 만나는가", "가장 크게 나누면 얼마인가"를 묻는 문제가 모두 이 두 값으로 풀립니다. 이 계산기는 숫자를 몇 개 넣든 결과와 함께 계산 과정, 소인수분해, 서로소 여부를 보여주므로 숙제 검산이나 실무 계산 모두에 쓸 수 있습니다.
계산 원리와 공식
유클리드 호제법은 GCD(a, b) = GCD(b, a mod b)라는 성질을 반복해 나머지가 0이 되면 그때의 나누는 수를 답으로 삼는 방법입니다. a와 b의 공약수는 b와 나머지 r의 공약수와 정확히 같기 때문에, 수를 줄여 가도 답이 변하지 않습니다. 큰 수에서는 소인수분해보다 훨씬 빠르고, 숫자가 수십 자리여도 단계 수가 수십 번 안팎에 그칩니다.
최소공배수는 LCM(a, b) = a ÷ GCD(a, b) × b로 구합니다. 곱을 먼저 하지 않고 나눗셈을 먼저 하는 것은 중간값이 불필요하게 커지는 것을 막기 위해서입니다. 세 수 이상이면 GCD(a, b, c) = GCD(GCD(a, b), c), LCM(a, b, c) = LCM(LCM(a, b), c)처럼 앞에서부터 차례로 묶습니다. 주의할 점은 "수들의 곱 ÷ GCD" 같은 식이 세 수 이상에서는 성립하지 않는다는 것입니다. GCD × LCM = a × b는 두 수일 때만 성립합니다.
소인수분해로 보면 더 직관적입니다. 각 소수에 대해 GCD는 입력한 수들의 지수 중 가장 작은 값을, LCM은 가장 큰 값을 취합니다. 예를 들어 12 = 2²×3, 18 = 2×3²이면 GCD는 2¹×3¹ = 6, LCM은 2²×3² = 36입니다.
유클리드 호제법 단계표 (1071과 462)
아래 표는 빌드 시점에 같은 알고리즘으로 계산한 것입니다. 나머지가 0이 되는 단계의 나누는 수(b)가 최대공약수입니다.
| 단계 | a | b | 몫 | 나머지 |
|---|---|---|---|---|
| 1 | 1071 | 462 | 2 | 147 |
| 2 | 462 | 147 | 3 | 21 |
| 3 | 147 | 21 | 7 | 0 |
3단계 만에 나머지가 0이 되었고 최대공약수는 21입니다. 최소공배수는 1071 ÷ 21 × 462 = 23,562입니다.
자주 나오는 숫자 쌍의 GCD·LCM 비교표
| 두 수 | GCD | LCM | 서로소 | 검산 (GCD × LCM) |
|---|---|---|---|---|
| 8, 12 | 4 | 24 | 아니오 | 4 × 24 = 96 (= 8 × 12) |
| 12, 18 | 6 | 36 | 아니오 | 6 × 36 = 216 (= 12 × 18) |
| 48, 180 | 12 | 720 | 아니오 | 12 × 720 = 8,640 (= 48 × 180) |
| 84, 126 | 42 | 252 | 아니오 | 42 × 252 = 10,584 (= 84 × 126) |
| 15, 28 | 1 | 420 | 예 | 1 × 420 = 420 (= 15 × 28) |
| 360, 84 | 12 | 2,520 | 아니오 | 12 × 2520 = 30,240 (= 360 × 84) |
15와 28처럼 GCD가 1인 서로소 쌍은 LCM이 두 수의 곱(420) 그대로 나옵니다. 서로소는 두 수가 소수일 필요가 없습니다. 15와 28은 둘 다 합성수이지만 공통 소인수가 없습니다.
소인수 지수로 보는 GCD와 LCM (360, 84, 90)
세 수를 소인수분해해 소수마다 지수를 나란히 놓으면 GCD는 열마다 가장 작은 지수, LCM은 가장 큰 지수로 만든 수입니다. 아래 표는 빌드 시점에 계산한 값입니다.
| 소수 | 360의 지수 | 84의 지수 | 90의 지수 | 최소 지수 | 최대 지수 |
|---|---|---|---|---|---|
| 2 | 3 | 2 | 1 | 1 | 3 |
| 3 | 2 | 1 | 2 | 1 | 2 |
| 5 | 1 | 0 | 1 | 0 | 1 |
| 7 | 0 | 1 | 0 | 0 | 1 |
최소 지수를 곱하면 GCD = 6, 최대 지수를 곱하면 LCM = 2,520입니다. 지수가 0이라는 것은 그 소수가 인수에 없다는 뜻이고, 한 수라도 0이면 최소 지수가 0이 되어 GCD에서 그 소수가 빠집니다. 이 도구의 계산 과정 칸에 소인수분해가 함께 나오므로 같은 방식으로 직접 대조해 볼 수 있습니다.
검산된 계산 예시
예시 1. 세 수 12, 18, 24. 먼저 GCD(12, 18) = 6, 다시 GCD(6, 24) = 6이므로 최대공약수는 6입니다. LCM은 LCM(12, 18) = 36, 다시 LCM(36, 24) = 72입니다. 12분·18분·24분 간격으로 도는 세 노선이 오전 6시에 동시에 출발했다면 다음 동시 출발은 72분 뒤, 즉 오전 7시 12분입니다.
예시 2. 타일 깔기, 가로 84cm × 세로 126cm. 정사각형 타일을 자르지 않고 틈 없이 깔려면 한 변이 84와 126의 공약수여야 하고, 가장 큰 타일은 GCD = 42cm입니다. 가로 2장, 세로 3장으로 총 6장이 필요합니다. 반대로 가로 2, 세로 3인 직사각형 벽돌로 정사각형을 쌓을 때 가장 작은 한 변은 LCM(2, 3) = 6입니다.
예시 3. 분수 통분, 5/12 + 7/18. 분모 12와 18의 LCM은 36이므로 15/36 + 14/36 = 29/36입니다. 분모의 곱 216으로 통분하면 숫자가 커지고 약분 단계가 늘어나므로 LCM을 쓰는 편이 효율적입니다.
더 보는 활용 시나리오
시나리오 A. 점검 주기 겹치기. 소화기 점검은 4일, 환기 필터 청소는 6일, 비품 재고 확인은 10일마다 한다면 세 작업이 같은 날 겹치는 주기는 LCM(4, 6, 10) = 60일이고, 세 주기의 GCD는 2이므로 같은 날 시작했다면 일이 생기는 날은 모두 시작일로부터 짝수 일째입니다. 겹치는 날 업무량이 몰리므로 한 작업의 시작일을 하루 늦추는 식으로 분산할 수 있습니다.
시나리오 B. 톱니바퀴 맞물림. 톱니 24개와 36개 기어가 맞물려 돌 때 두 기어가 처음 위치로 동시에 돌아오려면 맞물린 톱니 수가 LCM(24, 36) = 72개가 되어야 합니다. 이때 톱니 24개 기어는 72 ÷ 24 = 3바퀴, 36개 기어는 72 ÷ 36 = 2바퀴를 돕니다. 톱니 수의 GCD 12는 두 기어가 공유하는 가장 큰 톱니 단위이며, 72 = 24 × 36 ÷ 12로 LCM과 GCD 사이 항등식도 확인됩니다.
시나리오 C. 방 바닥 타일. 가로 360cm, 세로 240cm 바닥에 정사각형 타일을 자르지 않고 깔 때 가장 큰 변은 GCD = 120cm이고 필요한 장수는 (360 ÷ 120) × (240 ÷ 120) = 3 × 2 = 6장입니다. 한 변을 60cm로 줄이면 6 × 4 = 24장이 되는 식으로, 변이 GCD의 약수일 때만 틈 없이 깔 수 있습니다.
시나리오 D. 분수 세 개 더하기. 3/4 + 1/6 + 5/8의 분모 4, 6, 8의 LCM은 24이므로 18/24 + 4/24 + 15/24 = 37/24입니다. 분모의 곱 192 대신 24로 통분하면 숫자가 작아져 약분 단계가 줄어듭니다.
서로소와 쌍별 서로소의 차이
여러 수에서 "서로소"는 두 가지로 읽힐 수 있습니다. 이 도구가 표시하는 서로소 여부는 입력한 수 전체의 GCD가 1인지 보는 것입니다. 반면 "쌍별 서로소"는 어느 두 수를 골라도 GCD가 1이어야 합니다. 6, 10, 15를 예로 들면 전체 GCD는 1이지만 GCD(6, 10) = 2, GCD(10, 15) = 5, GCD(6, 15) = 3이라 쌍별 서로소는 아닙니다. 이때 LCM은 세 수의 곱 900이 아니라 30입니다. 쌍별 서로소인 수들만 LCM이 곱과 같아지므로, LCM을 곱으로 쉽게 구하려면 먼저 이 조건을 확인해야 합니다.
흔한 실수와 오해
- "최소공배수는 두 수의 곱"이라고 외우는 경우: 서로소일 때만 그렇습니다. 12와 18의 곱은 216이지만 LCM은 36입니다.
- 세 수 이상에 GCD × LCM = 곱 공식을 적용하는 경우: 두 수에서만 성립합니다. 12, 18, 24의 GCD 6과 LCM 72의 곱 432는 세 수의 곱 5184와 다릅니다.
- 약수와 배수를 혼동하는 경우: GCD는 입력한 수 중 가장 작은 수 이하이고, LCM은 가장 큰 수 이상입니다. 결과가 이 범위를 벗어나면 계산 실수입니다.
- 한 수가 다른 수의 약수인 경우를 놓치는 경우: 6과 24처럼 큰 수가 작은 수의 배수이면 GCD는 작은 수(6), LCM은 큰 수(24)입니다.
- 0과 음수: 수학적으로 GCD(0, n) = n 같은 정의가 있지만 일상 문제에서는 쓰이지 않아 이 도구는 양의 정수만 받습니다.
이 도구의 한계
입력은 1 이상 10억 이하의 정수로 제한합니다. 숫자가 많거나 서로 크게 다르면 LCM이 자바스크립트가 정확하게 표현하는 한계(약 9×10¹⁵)를 넘을 수 있으며, 이 경우 계산기는 잘못된 값을 보여주는 대신 안내 문구를 표시합니다. 암호학에서 쓰는 수백 자리의 큰 수나 다항식의 GCD는 다루지 않습니다.
한도에 걸리는 예를 들면 1,000,000,000과 999,999,999는 연속한 수라 서로소이고 LCM은 두 수의 곱 999,999,999,000,000,000으로 약 10¹⁸이어서 자바스크립트가 정확히 표현하는 정수 범위를 넘습니다. 이런 경우 오류 안내가 나오는 것이 정상 동작입니다. 반대로 GCD는 이런 큰 수에서도 정확하게 구해지므로 약분이나 비율 단순화만 필요하다면 입력 크기보다 GCD 값만 활용하세요. 유클리드 호제법은 큰 수에서도 빠르며, 연속한 피보나치 수(예: 89와 55)가 나머지 연산이 가장 많이 필요한 입력으로 알려져 있고 이 경우도 9단계면 GCD 1에 이릅니다.
결과 활용법
- 약분: 분수의 분자·분모를 GCD로 나누면 기약분수가 됩니다. 18/42는 GCD 6으로 나누어 3/7입니다.
- 균등 분배: 사과 48개와 배 180개를 남기지 않고 같은 구성으로 나누면 최대 12묶음(GCD)이고, 한 묶음은 사과 4개·배 15개입니다.
- 주기 맞추기: 교대 근무, 정기 점검, 반복 알림의 주기가 다를 때 LCM이 다시 겹치는 주기입니다.
- 비율 단순화: 해상도나 레시피의 비율을 가장 간단한 정수비로 줄일 때 GCD를 씁니다.
자주 묻는 질문
음수나 소수도 입력할 수 있나요?
이 계산기는 1 이상의 자연수만 지원합니다. 음수, 0, 소수를 입력하면 오류 메시지가 표시됩니다. 소수는 10의 거듭제곱을 곱해 정수로 바꾼 뒤 계산하고 결과를 다시 나누는 방법이 있습니다.
서로소(공약수가 1뿐인 관계)인지도 확인할 수 있나요?
네. 결과의 서로소 여부 칩이 "예"이면 입력한 수 전체의 최대공약수가 1입니다. 세 수 이상이면 "전체가 서로소"라는 뜻이며, 6, 10, 15처럼 어느 두 수끼리는 공약수가 있어도 전체 GCD가 1일 수 있습니다.
숫자를 몇 개까지 입력할 수 있나요?
개수 제한은 없지만 LCM이 매우 커질 수 있으므로 보통 2~6개를 권합니다. 쉼표뿐 아니라 공백으로 구분해도 인식합니다.
유클리드 호제법이 소인수분해보다 나은 이유는 무엇인가요?
소인수분해는 큰 수에서 약수를 찾는 데 시간이 오래 걸리지만, 유클리드 호제법은 나머지 연산만 반복하므로 단계 수가 자릿수에 비례하는 정도로 매우 빠릅니다. 다만 소인수분해는 지수를 비교해 "왜 그 값인지"를 설명하기에 좋아서 이 도구는 두 방식을 함께 보여줍니다.
GCD와 LCM이 같은 경우는 언제인가요?
입력한 수가 모두 같을 때만 그렇습니다. 예를 들어 7, 7의 GCD와 LCM은 모두 7입니다. 서로 다른 수가 하나라도 있으면 GCD는 가장 작은 수 이하, LCM은 가장 큰 수 이상이므로 같아질 수 없습니다.
같은 수를 여러 번 입력해도 되나요?
됩니다. 12, 12, 18처럼 중복된 수가 있어도 결과는 12, 18일 때와 같습니다. GCD와 LCM은 수의 개수가 아니라 값의 집합에만 달라지기 때문입니다.
1이 들어가면 결과가 어떻게 되나요?
1은 모든 수의 약수이므로 GCD는 항상 1이 되고, LCM은 1이 아닌 다른 수들의 LCM과 같습니다. 예를 들어 1, 12, 18의 LCM은 36입니다.
계산 결과를 손으로 검산하려면 어떻게 하나요?
두 수라면 GCD × LCM이 두 수의 곱과 같은지 확인하세요. 세 수 이상이면 앞의 두 수 결과를 먼저 검산하고 그 결과와 다음 수로 같은 확인을 반복하면 됩니다. 계산 과정 칸의 나눗셈 식은 모두 몫과 나머지를 보여 주므로 a = b × 몫 + 나머지가 맞는지 대조할 수 있습니다.
함께 쓰면 좋은 도구
- 소수 판별기: 입력한 수가 소수인지 확인할 때
- 화면 비율·해상도 계산기: 가로·세로의 GCD로 정수비를 구할 때
- 퍼센트 계산기: 비율을 백분율로 바꿀 때
- 공학용 계산기: 거듭제곱·로그 등 다른 수식을 계산할 때