유클리드의 알고리즘은 기원전 300년 경 그의 저서 「원론(Elements)」에 기록된 최대공약수를 구하는 방법을 말한다. 이 알고리즘은 그 타당성이 논리적으로 증명된 최초의 알고리즘이다. [^1]
유클리드 알고리즘은 「원론」 제7권에 있는 처음 세 정리에 의해 설명되고 있다. 「원론」 제7권은 22개의 정의로 시작된다. 요즘 수학과는 좀 다른 용어를 사용해서 정의가 표현되고 있으나, 이 7권의 시작 부분은 중요한 내용을 담고 있다. 지금의 용어로 약수, 배수, 짝수, 홀수, 솟수(prime number)[^2], 서로소, 합성수, 제곱수, 세제곱수, 완전수가 이 책의 처음에 정의되어 있다. 「원론」이 체계적으로 구성된 최초의 수학책이라는 의미에서 유클리드는 이 용어를 공식적으로 처음 정의한 사람이다.
「원론」 7권의 첫 정리는 서로 다른 두 수가 서로소임을 판별하는 법을 설명하고 있고, 두 번째 정리는 서로소가 아닌 다른 두 수의 최대공약수를 구하는 방법을 설명하고 있다. 세 번째 정리는 서로 다른 세 수의 최대공약수를 구하는 방법을 설명한다. 우리가 통상 유클리드 알고리즘 또는 유클리드 호제법이라고 부르는 것은 처음 두 정리를 합해 정리한 것이다.
유클리드 알고리즘을 현대적으로 정리하면 다음과 같지만,
두 정수 $a$, $b$($a \geq b$)에 대해 $a$를 $b$로 나눈 나머지를 $r$이라 하자. $a$와 $b$의 최대공약수를 $(a,b)$라 하면 $$(a,b) = (b,r)$$이다.
유클리드 시대에는 나눗셈이라는 용어를 쓰지 않았다. 유클리드 알고리즘의 원저자 버전은 다음과 같다.
7권 정리 1
두 개의 서로 다른 수가 주어졌을 때, 둘 중 작은 수로 큰 수를 빼는 작업을 반복하자. 이 과정에서 남는 수가 계속 생겨서 결국 1이 나온다면 처음 주어진 두 수는 서로소이다.
7권 정리 2
서로소가 아닌 두 수는 최대공약수를 가진다. [... 생략 ...] 작은 수로 더 큰 수를 반복해서 빼면 두 수가 서로소가 아니므로 1이 아닌 어떤 수가 다른 수의 약수가 된다. [... 생략...] 이 수가 두 수의 최대공약수이다.
위 인용에서 보이듯, 유클리드는 나눈다는 개념을 반복해서 뺀다는 것으로 표현했다. 두 수를 서로 빼는 작업이 복잡해 보이고 무엇과 무엇을 서로 계산해야 하는지가 헷갈릴 수 있는데, 이 과정을 기하학적으로 해석하면 쉬울 수 있다.
위 움짤은 38과 14의 최대공약수가 2임을 유클리드 알고리즘으로 설명하는 것이다.
일단은 가로 38, 세로 14인 직사각형을 그린다.
- 우선, $38=14 \times 2 + 10$이므로
14*14크기의 정사각형을 두 개 그릴 수 있다. 그러면10*14크기의 직사각형이 남는다. 이것은 38에서 14를 두 번 빼고 10이 남는다는 것을 의미한다. - $14 = 10 \times 1 + 4$이므로 앞에서 만들어진
10*14직사각형 안에10*10크기의 정사각형을 하나 그릴 수 있고10*4크기의 직사각형이 남는다. 이것은 14에서 10을 한 번 빼고 4가 남는다는 것을 의미한다. - $10 = 4 \times 2 + 2$이므로 앞에서 만든
10*4직사각형 안에4*4크기의 정사각형을 두 개 그릴 수 있고2*4크기의 직사각형이 남는다. 이것은 10에서 4를 두 번 빼고 2가 남는다는 것을 의미한다. - 마지막으로, $4= 2 \times 2$이므로 앞에서 만든
2*4크기의 직사각형 안에2*2크기의 정사각형을 두 개 그릴 수 있고 이것으로 처음 직사각형이 다 채워진다. 이것은 4에서 2를 두 번 빼고 아무것도 남지 않는다는 것이 된다. 따라서, 유클리드 알고리즘에 의해 38과 14의 최대공약수는 2이다.
위 그림은 38/14를 번분수로 만드는 데도 활용할 수 있다.
$$ \frac {38}{14} = \frac {19} 7 = 2 + \frac 5 7 = 2 + \dfrac{1} {\dfrac 7 5 } = 2 + \dfrac{1} {1 + \dfrac 2 5 } = 2 + \dfrac{1} {1 + \dfrac 1 {\dfrac 5 2} } = 2 + \dfrac{1} {1 + \dfrac 1 {2 + \dfrac 1 2} }$$
계산 과정을 잘 살펴보면 번분수 각 층에서 나오는 정수가 위에서 만든 정사각형 각각의 개수를 순서대로 나열한 것임을 알 수 있다.
이 알고리즘은 또 하나의 중요한 개념을 품고 있다. 중요한 것은, 유클리드도 언급했듯이, 이 작업이 무조건 유한번의 시도만에 끝난다는 것이다. 즉, 양의 유리수 비율을 가지는 직사각형을 위에서와 같이 직사각형에 포함될 수 있는 가장 큰 정사각형으로 채워가면 유한번만에 직사각형을 가득 채울 수 있다.
페르마의 마지막 정리를 증명했던 Andrew Wiles가 정수론에 입문할 때 처음으로 추천받았다던 책인 An Introduction to the Theory of Numbers (G. H. Hardy & E. M. Wright)에는 유클리드 알고리즘의 이 특성을 이용해서 황금비가 무리수임을 증명한 부분이 있다. 아래 영상에서 보듯이, 황금비 자체의 정의 때문에 가로/세로의 비율이 황금비인 직사각형을 위에서와 같이 정사각형으로 잘라내면 계속 처음 사각형과 닮음인 사각형이 얻어진다. 따라서, 위와 같은 작업을 유한번에 끝낼 수가 없다. 따라서, 황금비는 무리수라야 한다.
[^1]: 이집트, 바빌로니아에서도 일차방정식의 해를 구하거나 거듭제곱근의 해를 구하는 방법이 알려져 있었으나, 그 알고리즘의 타당성은 믿음의 영역이었다.
[^2]: 현재 국문법상으로는 '소수'라 표현해야 하지만, 국어사전에는 '소수'가 두 개 있다. 하나는 0.1, 3,14 등과 같이 소수점을 이용해서 표현하는 소수가 있다. [소수]라고 읽는다. 한편, 2, 3, 5, 7 등과 같이 두 개의 양의 약수를 가지는 수를 소수라고도 한다. 이 개념을 가진 소수는 [소쑤]라고 읽는다. 하지만, 이렇게 문맥상 처음 나타나거나 집합의 조건제시법과 같이 문맥 없이 단독으로 표현할 때는 어느 '소수'인지 알 수 없기 때문에 발음에 맞는 표현법이 옳다고 생각한다. 문법규칙보다는 의사소통이 더 중요하기도 하고, 한글은 표음문자이지 표의문자가 아니기 때문에 둘은 문자 수준에서 구별되어야 한다.