유클리드 호제법의 pseudo code와 증명

유클리드 호제법의 pseudo code

(출처 : kocw에 올라와있는 금오공대 자료구조 및 알고리즘 강의)

강의를 들으며 이 pseudo code를 보았고 이를 증명해보고자 한다.

유클리드 호제법의 증명

x = GCM p
y = GCM q
(p,q는 서로소, q > p)

y % x = GCM * (q % p)

x와 (y % x)의 최대공약수는 GCM이다.
왜냐하면 p와 q % p는 서로소이기 때문이다.
그리고 q%p 가 0이면 GCM은 x이다.

q와 p가 서로소이면 q%p 와 p가 서로소이거나 q%p가 0임을 증명해보자.

q%p와 p가 서로소가 아니라 가정해보자.
그럼 q % p와 p의 1이 아닌 공약수 r이 있고 q = p * (어떤 수) + q%p이므로 q와 p는 공약수 r을 가진다.

그리고 p와 q는 서로소이므로 p는 1일 수 있다.
그럼 GCM은 x이고 이 때 q % p = 0이다.
즉, GCM(x,y) = GCM(x%y , x)
그리고 GCM(0, x) 는 GCM(GCM 1, GCM n)일 때 나오므로
이 때 x는 GCM * 1 = GCM
GCM(0,x)의 값은 x를 리턴하게 하면 GCM을 구할 수 있다.

예시

GCM(12, 8)=
GCM(8, 12)=
GCM(4, 8) =
GCM(0, 4) = 4

활용해볼만한 문제

https://www.acmicpc.net/problem/2702

내 코드

#include <stdio.h>

int GCM(int a, int b)
{
	if (a == 0) return b;
	else return GCM(b % a, a);
}

int main()
{
	int a ,b, temp, i, T, G, L;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d %d", &a, &b);
		if (a > b)
		{
			temp = a;
			a = b;
			b = temp;
		}
		G = GCM(a, b);
		L = a * b / G;
		printf("%d %d\n", L, G);
	}
	return 0;
}

처음에 a가 b보다 작아야 한다고 생각해서 이렇게 작성했는데 생각해보니 a가 b보다 커도 자리가 GCM을 return하는 과정에서 자동으로 a와 b의 위치가 바뀌므로 이렇게 할 필요는 없었다.

수정한 코드

#include <stdio.h>

int GCM(int a, int b)
{
	if (a == 0) return b;
	else return GCM(b % a, a);
}

int main()
{
	int a ,b, temp, i, T, G, L;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d %d", &a, &b);
		G = GCM(a, b);
		L = a * b / G;
		printf("%d %d\n", L, G);
	}
	return 0;
}

여담으로 이 문제를 풀면서 a = GCM p, b = GCM q라 하면
최소공배수는 GCM p q 겠구나
그러면 LCM = GCM (a / GCM) (b / GCM) = a * b / GCM임을 알았다.
덕분에 옛날에 196ms였던 최대공약수, 최소공배수 문제를 0ms로 풀어내서 뿌듯했다.

앞으로 쓸 일이 있을 때마다 한번씩 다시 증명해보고 써보면 매우 유용할 것 같다.