중1 수학 - 최대공약수(Greatest Common Divisor, GCD)

최대공약수(Greatest Common Divisor, GCD)란?

두 개 이상의 자연수의 공약수 중에서 가장 큰 수를 **최대공약수(GCD)**라고 해.
예를 들어, 12와 18의 공약수는 1, 2, 3, 6이고, 이 중 가장 큰 6이 최대공약수야.

---

1. 최대공약수를 구하는 방법

(1) 약수를 나열하여 공통된 것 중 가장 큰 수 찾기

이 방법은 숫자가 작을 때는 유용하지만, 큰 수에서는 시간이 많이 걸려.

예제) 18과 24의 최대공약수

• 18의 약수: 1, 2, 3, 6, 9, 18
• 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
• 공약수: 1, 2, 3, 6
• 최대공약수(GCD) = 6

---

(2) 소인수분해를 이용하는 방법

두 수를 소인수분해하여 공통된 소인수의 곱으로 구하는 방법이야.

예제) 24와 36의 최대공약수

1. 소인수분해
   • 24 = 2 × 2 × 2 × 3
   • 36 = 2 × 2 × 3 × 3
2. 공통된 인수 찾기
   • 공통된 소인수: 2 × 2 × 3
3. 곱하기 → GCD(24, 36) = 2 × 2 × 3 = 12

✅ 이 방법은 큰 수에서도 사용 가능하지만, 소인수분해가 어려운 경우 비효율적일 수 있어.

---

(3) 유클리드 호제법을 이용하는 방법 (빠르고 효율적!)

유클리드 호제법은 큰 두 수의 최대공약수를 빠르게 구하는 방법이야.
원리는 큰 수를 작은 수로 나누고, 나머지를 이용해 반복적으로 최대공약수를 구하는 것이야.

유클리드 호제법 공식

• 두 수 a, b (단, a > b)에 대해
  • a를 b로 나눈 나머지를 r이라고 하면,
  • GCD(a, b) = GCD(b, r)
  • 이 과정을 나머지가 0이 될 때까지 반복

예제) 48과 18의 최대공약수

1. 48 ÷ 18 = 2, 나머지 12
2. 18 ÷ 12 = 1, 나머지 6
3. 12 ÷ 6 = 2, 나머지 0
4. 최대공약수 = 6

✅ 유클리드 호제법은 큰 수에도 빠르게 적용할 수 있어, 실생활에서 자주 사용해!

---

2. 최대공약수의 활용

(1) 분수의 약분

---

(2) 최소공배수와의 관계

---

(3) 서로소 관계 확인

• 최대공약수가 1이면 서로소라고 해.
• 예) 9와 28 → GCD(9, 28) = 1 → 서로소!

---

마무리 정리

✅ 최대공약수(GCD)는 두 수의 공약수 중 가장 큰 수
✅ 구하는 방법

• 약수 나열법 (숫자가 작을 때)
• 소인수분해법 (공통된 소인수 곱하기)
• 유클리드 호제법 (큰 수에서 효율적)
  ✅ 활용
• 분수 약분
• 최소공배수와의 관계
• 서로소 판별