유클리드 호제법이라고 알려져 있는 이 알고리즘은, 두 수의 최대 공약수를 찾아낼 수 있다. 어떤 두 자연수가 주어져 있다면, 이들을 나눌 수 있는 가장 큰 수를 최대 공약수라 한다. 만약, 이런 수가 1 이외에는 존재하지 않는다면, 이 두 수는 서로소 관계이다. 일반적으로, 최대 공약수를 찾아내는 것은, 주어진 수가 어떤 소수(Prime Number)로 구성되어 있는가를 알아냄으로 구할 수 있다. 즉, 소인수분해를 해보면 가장 확실하게 알 수 있다.
하지만, 소인수분해를 통한 방법은, 많은 시간을 소모한다는 단점이 있다. 유클리드 알고리즘은, 소인수분해를 필요로 하지 않으면서도, 빠르게 최대 공약수를 구할 수 있는 방법이다.
유클리드 알고리즘은 간단하다. 두 수 a, b가 주어졌을 때(a > b) a를 b로 나누고, 여기서 생긴 나머지와 몫을 계속해서 나누어서 나누어 떨어질 때까지 이것을 반복하는 것이다. 나누어 떨어질 때의 몫이 최대 공약수가 된다.
대수적으로 생각해 볼 수도 있겠지만, 여기서는 직관적으로 생각해보자.
어떤 두 수가 주어져 있고, 두 수를 공통으로 나눌 수 있는 최대 수를 찾고 싶다. 그렇다면, 먼저 큰 수를 작은수로 나눠본다. 왜냐하면, 이 경우 나누어 떨어진다면 바로 그 수가 우리가 원하는 답이기 때문이다. 하지만, 나누어 떨어지지 않는다면 나머지가 생기게된다.
a는 b만큼의 묶음으로 나뉘어져 있고, 문제는 나머지와 b의 관계이다. 즉, 나머지와 b를 공통으로 나눌 수 있는 어떤 수가 존재한다면, 이미 b만큼 나누어져 있는 이 묶음들을 이 공통의 수로 다시 묶어낼 수 있기 때문이다. 그리고, 이 과정을 나머지가 존재하지 않을 때까지 계속 반복한다. 예를 들어, gcd(1180, 482)를 구한다고 해보자.
1180 = 2 * 482 + 216이며, 1180은 두개의 482 묶음과, 216의 나머지가 생겼다. 여기서, 482와 216을 동시에 나눌 수 있는 수가 있다면 좋을 것이다. 우리는 나눌 수 있는 수 중 가장 커다란 수를 원하기 때문에, 482를 216으로 나눠본다. 나눠서 떨어진다면 이보다 더 좋을 수 없을 것이다.
482 = 2 * 216 + 50의 결과를 얻을 수 있으며, 216 두 묶음과 50이라는 나머지가 생겼다. 다시, 216을 50으로 나눠본다면 216 = 4 * 50 + 16이며, 50 = 3 * 16 + 2, 16 = 8 * 2로 딱 나누어 떨어지게 된다. 마지막에 얻어지는 2는 전 단계의 나머지인 16을 나눌 수 있고, 또 그 전 단계의 나머지인 50을 나눌 수 있으며, 또 그 전 단계의 나머지인 216을 나눌 수 있다. 이 모든 나머지를 공통적으로 나눌 수 있는 가장 커다란 수가 2이다.
그리고, 우리는 이 결과를 바탕으로 다음과 같은 정리를 이끌어 낼 수 있다.
Theorem. a, b가 두 정수이고, 최소 하나는 0이 아니라고 하자. gcd(a, b) = d라고 했을 때, ax + by = d를 만족하는 정수 x, y가 존재할 수 있으며, 특히 a와 b가 서로소라면 d = 1이다.
이것을 일반화하면, ax + by = gcd(a, b)라 할 수 있다. 유클리드 알고리즘을 조금 응용하면, x와 y를 손 쉽게 구할 수 있다. 먼저, 1180 = a, 482 = b라 하고, 위의 예를 대수로 정리해보면 다음과 같은 형태가 된다.
1180 = 2 * 482 + 216
482 = 2 * 216 + 50
216 = 4 * 50 + 16
50 = 16 * 3 + 2
16 = 8 * 2
이것을 다시 쓰면,
a = 2b + 216, 216 = a - 2b
b = 2(a - 2b) + 50, -2a + 3b = 50
a - 2b = 4(-2a + 3b) + 16, 9a - 14b = 16
-2a + 3b = 3(9a - 14b) + 2, -29a + 55b = 2
여기서 마지막에 얻어진 -29a + 55b = 2는, ax + by = gcd(a, b)의 형태이며, 우리가 원하는 x와 y값을 얻을 수 있다. 간결하면서도 아름답지 않은가?
Library/Mathematics