🔢
계산 공식
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) 방식으로 구합니다.
관련 계산기
½🔍🎲➗📐📊
분수 계산기
두 분수와 연산(+/-/×/÷)을 입력하면 기약분수, 소수, 대분수로 결과를 계산합니다. 약분도 지원합니다.
소수 판별 계산기
숫자를 입력하면 소수 여부와 소인수분해 결과를 즉시 확인할 수 있습니다.
순열·조합 계산기
n개 중 r개를 선택하는 조합(nCr)과 순열(nPr)을 계산합니다.
퍼센트 계산기
퍼센트 값 구하기, 백분율 구하기, 증감률 계산 등 다양한 퍼센트 계산을 간편하게 수행합니다.
비율 계산기
비율 간소화와 비례식 계산(A:B = C:D)의 미지수를 쉽게 구할 수 있는 비율 계산기입니다.
평균 계산기
숫자 목록을 입력하면 합계, 평균, 중앙값, 최빈값, 표준편차를 한번에 계산합니다.