최대공약수·최소공배수 정리: 유클리드 호제법과 활용
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
최대공약수(GCD)와 최소공배수(LCM)는 초등학교에서 배우지만,
분수 계산·공사 분배·주기 계산·심지어 현대 암호학(RSA)에서까지 핵심 도구로 쓰입니다.
두 개념의 정확한 정의, 빠르게 계산하는 두 가지 방법, 그리고 실생활 활용 사례를 한 번에 정리합니다.
최대공약수(GCD)란?#
두 수 이상의 공통 약수 중 가장 큰 수입니다.
- 약수(divisor): 어떤 수를 나누어 떨어지게 하는 수
- 공약수(common divisor): 두 수 이상의 공통 약수
- 최대공약수(GCD, Greatest Common Divisor): 공약수 중 가장 큰 값
영어로는 GCD, 약자로 GCF(Greatest Common Factor) 또는 HCF(Highest Common Factor)도 같은 뜻입니다.
예시: 12와 18의 최대공약수
12의 약수: 1, 2, 3, 4, 6, 12
18의 약수: 1, 2, 3, 6, 9, 18
공약수: 1, 2, 3, 6
최대공약수(GCD): 6
최소공배수(LCM)란?#
두 수 이상의 공통 배수 중 가장 작은 수입니다.
- 배수(multiple): 어떤 수에 자연수를 곱한 값
- 공배수(common multiple): 두 수 이상의 공통 배수
- 최소공배수(LCM, Least Common Multiple): 공배수 중 가장 작은 값
예시: 4와 6의 최소공배수
4의 배수: 4, 8, 12, 16, 20, 24, ...
6의 배수: 6, 12, 18, 24, ...
공배수: 12, 24, 36, ...
최소공배수(LCM): 12
GCD·LCM 계산 방법#
방법 1: 소인수분해#
두 수를 소인수분해한 후:
- GCD = 공통 소인수의 곱(지수는 작은 것 선택)
- LCM = 모든 소인수의 곱(지수는 큰 것 선택)
예시: 12와 18
12 = 2² × 3¹
18 = 2¹ × 3²
GCD = 2¹ × 3¹ = 6 (지수 작은 것 선택)
LCM = 2² × 3² = 36 (지수 큰 것 선택)
복잡한 예시: 60과 90
60 = 2² × 3¹ × 5¹
90 = 2¹ × 3² × 5¹
GCD = 2¹ × 3¹ × 5¹ = 30
LCM = 2² × 3² × 5¹ = 180
방법 2: 유클리드 호제법(빠른 GCD 계산)#
큰 수에서 작은 수로 나누기를 반복해 나머지가 0이 될 때의 제수가 GCD입니다. 기원전 300년 경 유클리드가 원론에 기록한 알고리즘으로, 현대 컴퓨터에서도 GCD 계산의 표준 방법입니다.
예시: GCD(48, 18) 계산
48 ÷ 18 = 2 ... 12 (48 = 18×2 + 12)
18 ÷ 12 = 1 ... 6 (18 = 12×1 + 6)
12 ÷ 6 = 2 ... 0 (12 = 6×2 + 0) ← 나머지 0
GCD(48, 18) = 6
소인수분해보다 큰 수에서 훨씬 빠릅니다. 100자리 수의 GCD도 1초 내 계산 가능합니다.
JavaScript 구현:
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
gcd(48, 18); // 6
gcd(123456, 654321); // 3
방법 3: GCD와 LCM의 관계#
LCM(a, b) = a × b ÷ GCD(a, b)
GCD를 먼저 구하면 LCM을 바로 계산할 수 있습니다.
예시: 48과 18의 LCM
LCM(48, 18) = 48 × 18 ÷ 6 = 864 ÷ 6 = 144
이 관계 덕분에 큰 수의 LCM도 유클리드 호제법 한 번이면 효율적으로 계산됩니다.
세 수 이상의 GCD·LCM#
세 수 이상은 두 수씩 묶어 반복합니다.
GCD(A, B, C) = GCD(GCD(A, B), C)
LCM(A, B, C) = LCM(LCM(A, B), C)
예시: GCD(12, 18, 24)
GCD(12, 18) = 6
GCD(6, 24) = 6
→ GCD(12, 18, 24) = 6
예시: LCM(4, 6, 10)
LCM(4, 6) = 12
LCM(12, 10) = 60
→ LCM(4, 6, 10) = 60
실생활 활용 사례#
1. 분수의 약분·통분#
약분: 분자와 분모의 GCD로 나누기
18/24 → GCD(18, 24) = 6 → 3/4
36/48 → GCD(36, 48) = 12 → 3/4
통분: 분모의 LCM을 공통 분모로 사용
1/4 + 1/6 → LCM(4, 6) = 12
= 3/12 + 2/12 = 5/12
2/9 + 5/12 → LCM(9, 12) = 36
= 8/36 + 15/36 = 23/36
분수 계산을 효율적으로 하려면 GCD·LCM이 필수입니다.
2. 공사·자재 분배#
바닥 타일을 자르지 않고 깔 때 타일 한 변의 최대 크기:
방 너비 360cm, 방 길이 480cm
타일 한 변의 최대 크기 = GCD(360, 480) = 120cm
다른 사례: 길이 132cm와 198cm의 두 막대를 자르지 않고 같은 길이로 절단하려면
한 조각의 최대 길이 = GCD(132, 198) = 66cm
132 ÷ 66 = 2조각, 198 ÷ 66 = 3조각, 총 5조각
3. 주기·순환 계산#
두 사건이 각각 A일, B일마다 반복될 때 동시에 발생하는 주기 = LCM(A, B)
예시 1: 버스 운행 주기
버스 A는 12분, 버스 B는 18분 간격 운행
→ LCM(12, 18) = 36분
→ 두 버스가 동시 출발하는 주기: 36분
예시 2: 신호등 동기화
신호등 A는 60초 주기, B는 90초 주기
→ LCM(60, 90) = 180초
→ 3분마다 두 신호등이 동시에 같은 색
예시 3: 행성 공전 주기
지구 365일, 화성 687일
→ LCM(365, 687) ≈ 250,755일 ≈ 687년
→ 지구·화성이 같은 위치 정렬에 가까운 주기 (정확한 천체 계산은 더 복잡)
4. 화면 해상도·비율#
1920×1080 해상도의 비율 계산:
GCD(1920, 1080) = 120
1920 ÷ 120 : 1080 ÷ 120 = 16 : 9
3840×2160 (4K):
GCD(3840, 2160) = 240
→ 16 : 9 (같은 비율)
영상·이미지 비율 계산, CSS aspect-ratio 설정에 활용됩니다.
5. 톱니바퀴·기계공학#
기어 두 개의 톱니 수가 12, 16개일 때 두 기어가 동시에 시작 위치로 돌아오는 회전 수:
LCM(12, 16) = 48
큰 기어: 48 / 16 = 3바퀴
작은 기어: 48 / 12 = 4바퀴
→ 큰 기어 3회전 / 작은 기어 4회전마다 동기화
6. 암호학: RSA 알고리즘#
현대 인터넷 보안의 RSA 암호 알고리즘은 두 거대 소수의 곱과 그들의 GCD 관계에 기반합니다. 공개키와 개인키 생성 시:
n = p × q (두 큰 소수)
φ(n) = (p−1)(q−1)
공개 지수 e: gcd(e, φ(n)) = 1 (서로소)
개인 지수 d: e × d ≡ 1 (mod φ(n))
GCD가 1이 되는 두 수(서로소)의 성질이 RSA 보안의 핵심입니다.
자주 묻는 질문#
Q. GCD가 1이면 어떤 의미인가요?
A. 두 수가 서로소(coprime, 공약수가 1뿐)라는 의미입니다. 예: GCD(7, 13) = 1, GCD(8, 9) = 1. 서로소인 두 수의 LCM은 두 수의 곱과 같습니다(LCM(a, b) = a × b).
Q. 0과 어떤 수의 GCD는?
A. 수학적으로 GCD(0, n) = n으로 정의합니다. 0은 모든 수로 나누어 떨어지므로 모든 수가 0의 약수이기 때문입니다.
Q. 음수의 GCD는 어떻게 계산하나요?
A. 일반적으로 절댓값을 기준으로 계산합니다. GCD(−12, 18) = GCD(12, 18) = 6.
Q. 소수만 있는 두 수의 GCD는?
A. 두 수가 서로 다른 소수면 GCD = 1입니다(서로소). 같은 소수면 GCD = 그 소수. 예: GCD(7, 11) = 1, GCD(13, 13) = 13.
Q. 컴퓨터에서 GCD를 어떻게 구현하나요?
A. 유클리드 호제법이 표준입니다. JavaScript의 단순 재귀 구현으로도 충분히 빠릅니다. Python에는 math.gcd() 내장 함수가 있고, Java에는 BigInteger.gcd()가 있습니다.
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const lcm = (a, b) => (a * b) / gcd(a, b);
Q. LCM이 너무 큰 수가 나올 수 있나요?
A. 네. 예를 들어 LCM(99, 100) = 9,900입니다. 두 수가 서로소이거나 큰 차이가 있으면 LCM이 두 수의 곱에 가까워져 매우 커집니다. 큰 수 처리는 GCD·LCM 계산기를 활용하세요.
Q. 분수 계산기에서 GCD가 어떻게 쓰이나요?
A. 분수 사칙연산 결과를 자동 약분할 때 GCD로 분자·분모를 나눕니다. 예: 24/36 → GCD(24, 36) = 12 → 2/3. 분수 계산기는 이 과정을 자동 수행합니다.
Q. 정수론에서 GCD의 중요한 정리는?
A. 베주 항등식(Bézout's identity): 두 정수 a, b의 GCD = d라면 ax + by = d를 만족하는 정수 x, y가 존재합니다. 확장 유클리드 호제법으로 이 x, y를 구할 수 있습니다. 이 정리는 RSA 키 생성, 모듈러 역원 계산, 디오판토스 방정식 풀이에 사용됩니다.
Q. 한국 수능에서 GCD·LCM 문제는 어떻게 출제되나요?
A. 수학 I·확률과 통계 단원에서 분수 계산, 주기 문제, 약수의 개수 등으로 등장합니다. 단순 계산보다 GCD·LCM의 성질을 활용한 응용 문제가 주를 이룹니다.
GCD·LCM 계산기 활용#
GCD·LCM 계산기에 두 수 이상을 쉼표 또는 공백으로 구분해 입력하면
GCD·LCM을 즉시 계산하고, 유클리드 호제법 단계와 소인수분해 결과를 함께 표시합니다. 큰 수(예: 12자리 이상)도 처리 가능합니다.
수학 학습을 더 진행하고 싶다면 순열·조합 완전 정리에서 경우의 수와 확률 기초를,
퍼센트 계산 완전 가이드에서 비율과 증감율을,
통계 계산 완전 가이드에서 평균·표준편차를 확인할 수 있습니다.