GCD 및 LCM은 분수 단순화, 방정식 풀기 및 문제 계획에 사용되는 기본 정수론 개념입니다. 여기에 모든 방법이 명확하게 설명되어 있습니다.
정의
GCD(최대 공약수) - GCF(최대 공약수) 또는 HCF(최고 공약수)라고도 함 - 두 숫자를 나머지 없이 나누는 가장 큰 양의 정수입니다.
**LCM(최소 공배수)**은 두 숫자로 나누어지는 가장 작은 양의 정수입니다.
GCD(a, b) × LCM(a, b) = a × b
이 관계는 하나를 찾으면 다른 하나를 계산할 수 있음을 의미합니다.
LCM(a, b) = (a × b) ÷ GCD(a, b)
방법 1: 소인수분해
최적의 용도: 이해, 더 작은 숫자, 한 번에 여러 숫자.
GCD 단계:
- 각 숫자를 소인수분해
- 공통 소인수 찾기
- 공통 인자의 최저 거듭제곱을 곱합니다.
LCM 단계:
- 각 숫자를 소인수분해
- 모든 소인수의 가장 거듭제곱을 곱합니다.
예: 36과 48의 GCD 및 LCM
소인수:
- 36 = 2² × 3²
- 48 = 2⁴ × 3
GCD: 공통 인수는 2와 3입니다. 가장 낮은 거듭제곱을 취합니다.
- GCD = 2² × 31 = 4 × 3 = 12
LCM: 모든 요인. 가장 높은 권한을 가지세요:
- LCM = 2⁴ × 3² = 16 × 9 = 144
검증: 36 × 48 = 1,728 = 12 × 144 ✓
방법 2: 유클리드 알고리즘(GCD)
최적의 용도: 큰 숫자 — 인수분해보다 훨씬 빠릅니다.
핵심 통찰력: GCD(a, b) = GCD(b, a mod b), 나머지가 0이 될 때까지 반복.
GCD(a, b):
while b ≠ 0:
r = a mod b
a = b
b = r
return a
예: GCD(252, 105)
| 단계 | 에이 | 비 | r = 모드 b |
|---|---|---|---|
| 1 | 252 | 105 | 42 |
| 2 | 105 | 42 | 21 |
| 3 | 42 | 21 | 0 |
GCD = 21 (0이 아닌 마지막 나머지)
예: GCD(1071, 462)
| 단계 | 에이 | 비 | 아르 자형 |
|---|---|---|---|
| 1 | 1071 | 462 | 147 |
| 2 | 462 | 147 | 21 |
| 3 | 147 | 21 | 0 |
글쿨 = 21
방법 3: 분할/래더 방법
최적의 대상: GCD와 LCM을 동시에 찾는 시각적 학습자.
두 숫자를 가장 작은 공통 소인수로 반복해서 나눕니다.
예: 12와 18의 GCD 및 LCM
2 | 12 18
3 | 6 9
| 2 3
GCD = 사용된 제수의 곱 = 2 × 3 = 6 LCM = 제수의 곱 × 나머지 숫자 = 2 × 3 × 2 × 3 = 36
두 개 이상의 숫자에 대한 LCM
예: LCM(4, 6, 10)
소인수:
- 4 = 2²
- 6 = 2 × 3
- 10 = 2×5
각 소수의 가장 높은 거듭제곱을 취합니다: 2² × 3 × 5 = 60
확인: 60 ¼ 4 = 15 ✓, 60 ¼ 6 = 10 ✓, 60 ¼ 10 = 6 ✓
실제 애플리케이션
분수 단순화: 분자와 분모를 GCD로 나눕니다.
- 24/36: GCD(24,36) = 12 → 24/36 = 2/3
분모가 다른 분수 더하기: 분모의 최소공배수(LCM)를 구합니다.
- 1/4 + 1/6: LCM(4,6) = 12 → 3/12 + 2/12 = 5/12
일정 문제: "버스 두 대가 동시에 출발합니다. 한 대는 12분 간격으로, 다른 한 대는 18분 간격으로 운행합니다. 언제 다시 함께 출발합니까?"
- LCM(12, 18) = 36 → 36분마다
자르기 재료: "보드는 36cm이고 다른 하나는 48cm입니다. 둘 다 낭비 없이 자를 수 있는 가장 긴 동일한 길이의 조각은 무엇입니까?"
- GCD(36, 48) = 12cm
빠른 정신 점검
GCD는 항상 ≤ 더 작은 숫자입니다 LCM은 항상 ≥ 더 큰 숫자입니다 GCD(a,b) = 1이면 숫자는 서로소입니다 — LCM(a,b) = a × b
예: GCD(7, 13) = 1(둘 다 소수, 공통 인수 없음) → LCM = 7 × 13 = 91