최대공약수는 무엇이며 어떻게 구하거나 계산하는지 알아봅시다. 유클리드 호제법과 증명(Greatest Common Divisor, GCD)

목차

1. 최대공약수, Greatest Common Divisor : GCD

2. 최대공약수 구하는 법 - 소인수 분해로 구하기

3. 최대공약수 구하는 법 - 유클리드 호제법

4. 유클리드 호제법 증명

 

320x100

 

1. 최대공약수, Greatest Common Divisor : GCD

최대공약수는 두 개의 수 A, B의 약수들 중 공통된 숫자 중 최대 수를 가르키는 것입니다.

숫자가 많아져도 역시 최대공약수는 존재합니다.

현대사회에 들어서면서 컴퓨터를 통해 언어로 표현조차 안되는 양의 숫자들의 연산이 가능해지면서,

각 숫자들의 관계를 파악해주는 공약수가 매우 중요한 팩터가 되었습니다.

 

 

2. 최대공약수 구하는 법 - 소인수 분해로 구하기

 

소인수 분해를 한 후에 공통적인 숫자만 골라내면 됩니다.

 

(예시 - 24, 60, 84의 최대공약수 구하기)

 

24 = 2 × 2 × 2 × 3

60 = 2 × 2 × 3 × 5

84 = 2 × 2 × 3 × 7

 

이 숫자들은 모두 2를 두 개, 3을 하나 포함하고 있습니다.

최대공약수는 12 = 2 × 2 × 3이 됩니다.

작은 수들의 연속일 때는 이 것도 좋은 방법이죠.

하지만 큰 수 일 때는 더 좋은 방법이 있습니다.

 

 

3. 최대공약수 구하는 법 - 유클리드 호제법

 

고대 그리스의 수착자인 유클리드는 기학학 원론(유클리드 원론)으로 유명합니다.

총 13개권으로 정리된 이 책은 100% 유클리드에 머리속에서 나온 것은 아니고, 정리본에 가깝습니다.

하지만 기하학과 정수론의 시초로 알려진 책으로 공리를 제안하고 있다는 데서 수학의 시초라 불립니다.

 

이 원론에 내용 중의 호제법은 인류 최초의 알고리즘으로 최대 공약수를 구하는 법이 기록되어 있습니다.
두 정수 A, B의 최대공약수를 GCD(A, B)라고 하자.
정수 A, B, q r (b ≠ 0)에 대하여 A = Bq + r이면 GCD(A, B) = GCD(B, r)가 성립한다.
- 네이버 지식백과 -

 

그러니까 A, B의 관계를 A = Bq + r로 나타내면 A, B와 B, r의 최대공약수는 같다는 말입니다.

예시를 보시면 알 수 있습니다.

예를 들어 2,056,512와 123,456의 최대공약수를 구해 보겠습니다.

이 정도 수의 약수를 구하라고 하면 손으로 계산하는 경우는 포기하기 딱 좋은 큰 수입니다.

호제법은 여러번 반복해야 합니다.

 

호제법의 사용

 

마지막은 나머지가 없습니다. 바로 이 때 192가 바로 최대공약수입니다.

처음에는 접근이 어렵다고 생각한 큰 수도 7번 반복하면 구해지네요.

손으로 하려면 번거롭기는 합니만 구할 수 있는 방법이 있는 것 자체가 좋은 일일 겁니다.

그래도 역시 프로그램으로 알고리즘을 짜두는게 편리하겠죠.

큰 수도 몇번만 연산하면 계산할 수 있으니 컴퓨터의 연산속도로는 상상도 못 하는 단위도 처리할 수 있습니다.

 

 

4. 유클리드 호제법 증명

호제법의 증명을 잠시 소개합니다.

 

이렇게 정리를 했으면 아래 식부터 시작해서 증명하겠습니다.

 

 

따라서 G역시 r의 약수입니다.

또한 G'은 최대공약수임으로 G는 G'의 약수입니다.

여기까지 G는 B와 r, G'의 약수가 됩니다.

 

 

여기서 m은 b의 약수을 알 수 있습니다.
지금까지 알아낸 바로,

 

 

이로서 m은 a와 b의 공약수임을 알았습니다.

a, b는 서로소임으로 공약수는 1뿐입니다. 

m=1이고, G'=mG=G 고로 G=G'입니다.

 

 

 

---

최소 공배수 부분에서 설명드리겠지만, 최대공약수가 있으면 최소 공배수도 구할 수 있습니다.

이 공약수 공배수는 알고리즘이 완성되어 대부분의 수학툴에서 사용할 수 있습니다.