최대공약수(GCD)와 최소공배수(LCM)란?
최대공약수(GCD, Greatest Common Divisor)는 두 수를 모두 나누는 약수 중 가장 큰 수입니다. 최소공배수(LCM, Least Common Multiple)는 두 수의 공통 배수 중 가장 작은 수입니다. 두 개념은 분수 약분·통분, 톱니바퀴 회전 주기, 타일 깔기 같은 실생활 문제에 반드시 등장합니다.
유클리드 호제법 — 단계별 예시
유클리드 호제법은 "큰 수를 작은 수로 나눈 나머지"를 반복해서 GCD를 구하는 알고리즘입니다. 나머지가 0이 될 때 마지막 나누는 수가 GCD입니다.
예: GCD(48, 18) 계산
| 단계 | 큰 수 (a) | 작은 수 (b) | 나머지 (a mod b) | 다음 단계 |
|---|---|---|---|---|
| 1 | 48 | 18 | 48 mod 18 = 12 | a=18, b=12 |
| 2 | 18 | 12 | 18 mod 12 = 6 | a=12, b=6 |
| 3 | 12 | 6 | 12 mod 6 = 0 | 종료 → GCD = 6 |
코드로 나타내면 다음과 같습니다.
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a; // b가 0이 되는 순간의 a가 GCD
}
LCM은 GCD를 구한 뒤 다음 공식으로 계산합니다.
LCM(A, B) = (A × B) / GCD(A, B)
GCD(48, 18) = 6이므로 LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144입니다.
소인수분해로 GCD·LCM 구하기
소인수분해를 이용하면 GCD와 LCM을 더 직관적으로 이해할 수 있습니다.
예: 48과 18의 소인수분해
| 수 | 소인수분해 | 2의 지수 | 3의 지수 |
|---|---|---|---|
| 48 | 2^4 × 3^1 | 4 | 1 |
| 18 | 2^1 × 3^2 | 1 | 2 |
| GCD | 공통 소인수의 최솟값 지수 | min(4,1)=1 | min(1,2)=1 |
| LCM | 공통 소인수의 최댓값 지수 | max(4,1)=4 | max(1,2)=2 |
- GCD = 2^1 × 3^1 = 6
- LCM = 2^4 × 3^2 = 16 × 9 = 144
GCD × LCM = A × B 관계식
두 수의 GCD와 LCM 사이에는 항상 다음 등식이 성립합니다.
A × B = GCD(A, B) × LCM(A, B)
48 × 18 = 864, 6 × 144 = 864로 일치합니다. 이 관계식은 "GCD를 알면 LCM을 바로 구할 수 있다"는 의미이기도 합니다. 본 계산기는 결과 아래에 이 등식을 자동으로 검증해서 보여줍니다.
실생활 활용 — 톱니바퀴와 타일 깔기
| 상황 | 사용 개념 | 예시 |
|---|---|---|
| 분수 약분 | GCD | 12/18 → GCD(12,18)=6 → 2/3 |
| 분수 통분 | LCM | 1/4 + 1/6 → LCM(4,6)=12 → 3/12 + 2/12 |
| 톱니바퀴 회전 | LCM | 12칸·18칸 톱니바퀴가 다시 같은 위치 → LCM(12,18)=36번 회전 후 |
| 정사각형 타일 | GCD | 48cm×18cm 방을 가장 큰 정사각형 타일로 → GCD(48,18)=6cm 타일 |
| 버스 배차 겹침 | LCM | 12분·18분 간격 버스 → LCM(12,18)=36분마다 동시 출발 |
톱니바퀴 심화
이 개념 중 가장 자주 시험에 나오는 것이 톱니바퀴 문제입니다. 톱니가 A개인 바퀴와 B개인 바퀴가 맞물려 있을 때, 두 바퀴가 처음 상태로 돌아오려면 총 LCM(A, B)개의 톱니가 지나야 합니다. 이때 A 바퀴는 LCM÷A번, B 바퀴는 LCM÷B번 회전합니다.
타일 깔기 심화
가로 A cm, 세로 B cm인 직사각형 방을 남김 없이, 가장 크게 정사각형 타일로 채우려면 한 변의 길이가 GCD(A, B)인 타일을 쓰면 됩니다. 타일 개수는 (A÷GCD) × (B÷GCD)장입니다.
세 수의 GCD·LCM
세 수 A, B, C의 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
LCM(12, 18, 24) → LCM(12, 18) = 36 → LCM(36, 24) = 72
서로소(Coprime)란?
두 수의 GCD가 1인 경우, 두 수는 서로소라고 합니다. 예를 들어 GCD(7, 13) = 1이므로 7과 13은 서로소입니다. 서로소인 두 수는 LCM = A × B가 됩니다. 암호학(RSA)과 중국인의 나머지 정리 같은 고급 수학에서도 서로소 개념이 핵심적으로 등장합니다.