최대공약수 구하는 법 쉽게 계산하기

 

최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 수의 공통된 약수 중 가장 큰 수를 의미합니다. 최대공약수를 구하는 방법을 단계별로 설명하겠습니다.

 

1. 최대공약수의 개념 이해하기

최대공약수는 주어진 수들의 공통된 약수 중에서 가장 큰 값을 말합니다. 예를 들어, 12와 18의 공통된 약수는 1, 2, 3, 6이지만, 이 중에서 가장 큰 값은 6입니다. 따라서 12와 18의 최대공약수는 6입니다.

2. 최대공약수 구하는 방법

방법 1: 나열법

1. 각 수의 약수를 나열합니다.
   - 예: 12와 18의 약수를 나열
     - 12의 약수: 1, 2, 3, 4, 6, 12
     - 18의 약수: 1, 2, 3, 6, 9, 18
2. 두 수의 공통된 약수 중 가장 큰 수를 찾습니다.
   - 12와 18의 공통된 약수: 1, 2, 3, 6
   - 따라서, 최대공약수는 6입니다.

방법 2: 소인수분해법

1. 각 수를 소인수분해 합니다.
   - 예: 48과 60의 소인수분해
     - 48 = 2^4 × 3
     - 60 = 2^2 × 3 × 5
2. 공통된 소인수 중 가장 작은 차수를 찾습니다.
   - 2의 최소 차수: 2^2
   - 3의 최소 차수: 3
   - 공통된 소인수는 2와 3입니다.
3. 공통된 소인수의 곱을 구합니다.
   - 2^2 × 3 = 4 × 3 = 12
   - 따라서, 48과 60의 최대공약수는 12입니다.

방법 3: 유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 구하는 효율적인 알고리즘입니다.

1. 두 수 중 큰 수를 a, 작은 수를 b라고 합니다.
   - 예: a = 56, b = 42
2. a를 b로 나눈 나머지를 r이라고 합니다.
   - 56 ÷ 42 = 1 (나머지 14)
   - 따라서, r = 14
3. a를 b로, b를 r로 바꿉니다.
   - a = 42, b = 14
4. 나머지가 0이 될 때까지 이 과정을 반복합니다.
   - 42 ÷ 14 = 3 (나머지 0)
   - 나머지가 0이므로, 이 때의 b값이 최대공약수입니다.
   - 따라서, 최대공약수는 14입니다.

 

3. 예제 문제 풀이

예제 1: 24와 36의 최대공약수

- 나열법: 24의 약수 (1, 2, 3, 4, 6, 8, 12, 24)와 36의 약수 (1, 2, 3, 4, 6, 9, 12, 18, 36) 중 가장 큰 공통된 약수는 12입니다.
- 소인수분해법: 24 = 2^3 × 3, 36 = 2^2 × 3^2. 공통된 소인수는 2^2 × 3 = 4 × 3 = 12.
- 유클리드 호제법:
  - a = 36, b = 24
  - 36 ÷ 24 = 1 (나머지 12)
  - a = 24, b = 12
  - 24 ÷ 12 = 2 (나머지 0)
  - 따라서, 최대공약수는 12.

예제 2: 48과 180의 최대공약수

- 나열법: 48의 약수 (1, 2, 3, 4, 6, 8, 12, 16, 24, 48)와 180의 약수 (1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180) 중 가장 큰 공통된 약수는 12입니다.
- 소인수분해법: 48 = 2^4 × 3, 180 = 2^2 × 3^2 × 5. 공통된 소인수는 2^2 × 3 = 4 × 3 = 12.
- 유클리드 호제법:
  - a = 180, b = 48
  - 180 ÷ 48 = 3 (나머지 36)
  - a = 48, b = 36
  - 48 ÷ 36 = 1 (나머지 12)
  - a = 36, b = 12
  - 36 ÷ 12 = 3 (나머지 0)
  - 따라서, 최대공약수는 12.

 

이처럼 최대공약수를 구하는 방법은 여러 가지가 있으며, 상황에 따라 가장 편리한 방법을 선택하면 됩니다. 이 글을 통해 최대공약수를 구하는 법을 쉽게 이해할 수 있기를 바랍니다.