두 수의 최대 공약수를 구하는 알고리즘 - 유클리드 호제법의 파이썬 구현과 수학적 증명

두 수의 최대공약수를 구하는 방법?

중학교때 가장 일반적으로 배우는 방법은 두 수가 서로소가 될때까지 공통 약수로 나눠간 후 공통 약수들을 곱하여 구하는 것이다. 

그치 그치 그게 제일 흔하고 직관적이지! 그런데 컴퓨터로 구현시 더 간단한 알고리즘이 있다! 바로바로 유클리드 호제법. 더 간단하지만 살짝은 추상적이다. 

유클리드는 영어식 이름. 그리스식 이름은 에우클레이데스라고 합니다.

호제법은 서로 나눈다라는 뜻이다.

유클리드 호제법은 두 수를 서로 나누어 가며 최대공약수를 구하는 방법이다. 두 수의 최대공약수는, 두수를 서로 나눈 나머지와 두 수중 더 작은 수의 최대공약수와 같다. 그래서 두 수를 나머지가 0이 될때까지 서로 나눠가며 그 나머지끼리 최대공약수를 구하는 것이다. 

 

예를 들어 48과 64를 생각해보면...

64와 48의 최대공약수 = 64 % 48 과 48의 최대공약수 

                                  = 16과 48의 최대공약수

                                  = 48 % 16 과 16의 최대공약수....... 앗 그런데 48%16 == 0 이므로 우리가 구하고자 했던 최대공약수는 16이다.

 

뭐 대충 프로세스는 이러하다~!

 

이에관한 수학적 증명은..

와.. 중학생때 유클리드 기하학(중딩용)이라는 책에서 잠깐 보고 넘어간 기억이 있는데 파이썬 공부하면서 다시 찾아볼 줄이야.....

증명하고자 하는 명제.

A와B의 최대공약수가 G이면, A%B(=r)와 B의 최대공약수도 G이다.

전제 1 

A = G*a

B = G*b 

G는 A와 B의 최대공약수. 단, a, b는 서로소

 

전제 2

A = q B + r

즉 A를 B로 나눈 나머지를 r이라 하자.

 

추론 1 

전제 1과 전제 2로부터

G a = G q b + r

따라서 r = G (a- qb)

 

이때 B = Gb이므로 r과 B의 최대공약수가 G이기 위해서는 a-qb와 b이 서로소임을 증명하면 된다. 

 

소증명 'a-qb와 r은 서로소이다'

본증명을 위한 소증명을 하기 위해 귀류법을 사용한다. 

a-qb와 b은 서로소가 아니라고 가정했을 때 전제에서 논리적 오류를 찾아내는 것이다. 

a-qb = m*n

b = m*k 

따라서 둘은 m이라는 공약수를 가진다고 가정해보자.

위 식으로부터, a = qmk + mn = m(qk + n)으로 a도 m을 약수로 갖는다.

이는 처음 전제인 a와 b는 서로소가 아니다에 반하므로 a-qb와 b는 서로소이다.

 

따라서 A와 B의 최대공약수 G는 r과 B의 최대공약수와 같다. 

 

이를 파이썬 코드로 구현해보았다. 

 

def find_gcd(a,b):
    while (b!=0):
        a, b = b, a%b
    return a