🔢
계산 공식
GCD: 유클리드 호제법 | LCM = a × b ÷ GCD(a, b)유클리드 호제법으로 최대공약수를 구한 후, 두 수의 곱을 최대공약수로 나눠 최소공배수를 계산합니다.
최대공약수(GCD)와 최소공배수(LCM) 핵심 공식
| 항목 | 설명 | 공식 |
|---|---|---|
| GCD (최대공약수) | 두 수의 공약수 중 가장 큰 수 | 유클리드 호제법 |
| LCM (최소공배수) | 두 수의 공배수 중 가장 작은 수 | LCM = a × b ÷ GCD |
| 관계식 | GCD × LCM = a × b | 항상 성립 |
유클리드 호제법 (최대공약수 구하기)
GCD(a, b) = GCD(b, a mod b) — a mod b = 0이 될 때까지 반복
예시: GCD(48, 18)
- GCD(48, 18) = GCD(18, 48 mod 18) = GCD(18, 12)
- GCD(18, 12) = GCD(12, 18 mod 12) = GCD(12, 6)
- GCD(12, 6) = GCD(6, 12 mod 6) = GCD(6, 0) = 6
자주 묻는 GCD·LCM 계산 예시
| 두 수 | GCD | LCM |
|---|---|---|
| 12, 18 | 6 | 36 |
| 15, 25 | 5 | 75 |
| 24, 36 | 12 | 72 |
| 100, 75 | 25 | 300 |
| 7, 13 | 1 | 91 |
| 14, 21 | 7 | 42 |
소인수분해로 GCD·LCM 구하기
소인수분해 후 공통/합집합 소인수를 이용하는 방법입니다.
GCD: 공통 소인수만, 더 작은 지수 사용 LCM: 모든 소인수를, 더 큰 지수 사용
예시: GCD(180, 120)
- 180 = 2² × 3² × 5
- 120 = 2³ × 3 × 5
- GCD = 2² × 3 × 5 = 60
- LCM = 2³ × 3² × 5 = 360
실생활 활용 사례
| 상황 | GCD 또는 LCM | 사용 |
|---|---|---|
| 분수 약분 | GCD | 12/18 → GCD=6 → 2/3 |
| 분수 통분 | LCM | 1/4 + 1/6 → LCM=12 → 3/12+2/12 |
| 타일 쪼개기 | GCD | 60cm × 48cm 방을 최대 크기로 |
| 버스 배차 주기 | LCM | A버스 15분, B버스 20분 → LCM=60분마다 동시 출발 |
| 등분할 | GCD | 36개, 24개를 같은 수로 나누기 → GCD=12 → 12묶음 |
GCD가 1인 경우 (서로소)
두 수의 GCD가 1이면 서로소(relatively prime) 라고 합니다.
- 예: GCD(7, 13) = 1 → 7과 13은 서로소
- LCM(7, 13) = 7 × 13 = 91 (두 수의 곱이 LCM)
- 서로소인 두 수의 LCM은 항상 두 수의 곱과 같습니다
자주 묻는 질문
최대공약수는 어디에 쓰이나요?
분수 약분(12/18 → GCD=6 → 2/3), 물건을 균등하게 나누기(36개와 24개를 GCD=12 → 각 3개, 2개씩 12묶음), 도형의 최대 공통 타일 크기 계산에 사용합니다. GCD는 '두 수량을 공통 단위로 쪼갤 때의 최대 단위'입니다.
최소공배수는 어디에 쓰이나요?
분수 통분(1/4 + 1/6: LCM=12), 두 사건이 동시에 발생하는 주기(버스 A 15분, B 20분 → LCM=60분마다 동시 출발), 프로그래밍의 타이밍 동기화, 톱니바퀴 문제 등에 사용합니다.
유클리드 호제법이 빠른 이유는?
일일이 공약수를 나열하지 않고 나머지 연산을 반복해 단계를 줄입니다. GCD(123456, 78901) 같은 큰 수도 몇 번의 나머지 계산으로 빠르게 구합니다. 시간 복잡도는 O(log min(a,b))로 매우 효율적입니다.
GCD × LCM = a × b가 항상 성립하나요?
예. GCD(a,b) × LCM(a,b) = a × b는 항상 성립합니다. 예: GCD(12,18)=6, LCM=36 → 6×36=216=12×18. 이 관계를 이용해 GCD를 알면 LCM을, LCM을 알면 GCD를 쉽게 구할 수 있습니다.
세 수의 GCD와 LCM은 어떻게 구하나요?
세 수 a, b, c의 GCD: GCD(GCD(a,b), c)로 순서대로 계산합니다. 예: GCD(12,18,24) = GCD(GCD(12,18),24) = GCD(6,24) = 6. LCM도 마찬가지로 LCM(LCM(a,b),c) 방식으로 구합니다.