[수학] GCD(최대공약수), LCM(최소공배수)

GCD(최대공약수), LCM(최소공배수) 정리

수학 및 프로그래밍에서 자주 사용되는 GCD(최대공약수)와 LCM(최소공배수)에 대해 개념, 관계, 구현 방법까지 정리한 문서입니다.

---

1. GCD(최대공약수)란?

• 두 수의 공통된 약수 중 가장 큰 수
• 예: GCD(12, 18) = 6
  • 12의 약수: 1, 2, 3, 4, 6, 12
  • 18의 약수: 1, 2, 3, 6, 9, 18
  • 공약수: 1, 2, 3, 6 → 최대공약수는 6

---

2. LCM(최소공배수)란?

• 두 수의 공통된 배수 중 가장 작은 수
• 예: LCM(12, 18) = 36
  • 12의 배수: 12, 24, 36, 48, …
  • 18의 배수: 18, 36, 54, 72, …
  • 공배수: 36, 72, … → 최소공배수는 36

---

3. GCD와 LCM의 관계

GCD와 LCM은 다음의 중요한 관계식을 가집니다:

\[\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b\]

따라서,

\[\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}\]

• 이 관계는 항상 성립하며, LCM을 GCD 기반으로 효율적으로 계산할 수 있습니다.

---

4. 유클리드 호제법

• GCD를 구하는 가장 효율적인 알고리즘
• 원리: 나머지를 이용하여 두 수를 서로 나누면서 반복

수식:

\(\text{GCD}(a, b) = \text{GCD}(b, a \bmod b)\)

종료 조건:

\(\text{GCD}(a, 0) = a\)

구현 예시 (C++)

int GCD(int a, int b) {
    return b == 0 ? a : GCD(b, a % b);
}

인자의 대소관계는 상관없다

• 유클리드 호제법은 a > b 뿐 아니라 a < b여도 동작함
• % 연산자와 재귀를 통해 큰 값이 앞으로 오게 되며, 결국 b == 0이 될 때 최대공약수로 수렴

예제 비교:

GCD(12, 18)
→ GCD(18, 12)
→ GCD(12, 6)
→ GCD(6, 0) = 6

GCD(18, 12)
→ GCD(12, 6)
→ GCD(6, 0) = 6

→ 결과는 항상 같음

---

5. LCM 구현

GCD를 활용하여 LCM을 구할 수 있습니다

int LCM(int a, int b) {
    return a / GCD(a, b) * b; // 오버플로 방지를 위해 a를 먼저 나눔
}

---

6. 예제 코드

#include <iostream>
using namespace std;

int GCD(int a, int b) {
    return b == 0 ? a : GCD(b, a % b);
}

int LCM(int a, int b) {
    return a / GCD(a, b) * b;
}

int main() {
    int a = 12, b = 18;
    cout << "GCD: " << GCD(a, b) << endl; // 6
    cout << "LCM: " << LCM(a, b) << endl; // 36
}

---

7. 호제법이란?

• 한자어 互除法:
  • 互(호): 서로
  • 除(제): 나누다
  • 法(법): 방법

→ “서로서로 나누는 방식”으로 최대공약수를 구하는 방법

• 유래: 고대 그리스 수학자 유클리드의 『기하학 원론(Elements)』
• 영어로는 Euclidean Algorithm이라 함

---

8. 요약 표

항목	의미	예시 (a = 12, b = 18)
GCD	최대공약수	6
LCM	최소공배수	36
관계식	GCD × LCM = a × b	6 × 36 = 12 × 18
유도 방식	유클리드 호제법	재귀적 나머지 계산
대소관계 영향	없음	순서 바꿔도 동일