유클리드 호제법에 대한 쉬운 설명과 증명

유클리드 호제법 정도의 유명한 알고리즘은

위키백과 정도만 봐도 잘 설명되어 있는데,

조금 더 간결한 설명을 원하시는 분들을 위해서 글을 써보기로 했어요.

 

 

인터넷에선 수학적으로 너무 잘 설명된 글이나

아니면 증명 없이 코드만 박아둔 글이 많아서요;;;

 

유클리드 호제법은,

(적어도 우리가 일반적으로 알고리즘 문제를 풀 때에는,)

두 자연수의 최대공약수를 빠르게 구하기 위해 이용되는 알고리즘이에요.

 

쪼끔 더 문자를 써서 표현하자면,

두 자연수 A, B의 최대공약수 G를 빠르게 구하기 위해서 이용하며,

A>B일 때 G(A, B)와 G(A%B, B)가 같다는 점을 이용해요.

 

코드는 아래와 같겠죠.

 

int gcd(int a, int b) {
	if (a < b) swap(&a, &b);
	return b != 0 ? gcd(b, a % b) : a;
}

 

a, b라는 두 자연수가 있고, 두 수의 최대공약수가 G이고, a>b일 때 증명해볼게용.

a=GA, b=GB라고 표현할 수 있어요. 그리고 여기서 A, B는 서로소겠죠?

그리고 a=bq+r이라고 표현할 수 있어요. a>b이니까요.

 

여기다가 a=GA, b=GB를 대입하면... GA=GBq+r이 됩니다.

이걸 좀 깔짝이면

GA-GBq=r

G(A-Bq)=r

이렇게 변형할 수 있어요.

 

근데 위 식과 같이, b=GB라는 사실을 생각해보세요.

좀 더 눈에 잘 보이게 하면...

r=G*(A-Bq)

b=G*B

그러면 G는 r과 b의 공약수이네요.

 

근데 정말로 여기서 G가 최대공약수라면, A-Bq와 B가 서로소여야겠죠?

그게 아니라면 G는 최대공약수가 아니니까요.

 

귀류법을 써서...

A-Bq와 B가 서로소가 아니라고 해봅시다.

A-Bq = mt이고 B = nt인 t>1이 존재해야겠죠.

그런데 B = nt를 A-Bq = mt에 대입하면 A-Bq = A-ntq = mt라는 식이 나오고요,

A=mt+ntq

A=t(m+nq)가 됩니다.

어라, 근데... B=nt라고 했는데, 그러면 A, B가 t라는 1보다 큰 공약수를 가지네요?

그럼 A, B가 서로소가 아니니까 모순이 발생했습니다.

즉, A-Bq는 B가 서로소라는 명제는 참입니다.

 

증명까지 끝냈어용

 

복잡하지만 초등학생도 따라올 수 있을 정도로, 어려운 증명 과정은 전혀 없어요!

 

이상으로 유클리드 호제법에 대한 간결하지만 쓸 거 다 쓴 정리 끝!