최대공약수와 유클리드 호제법(GCD and the Euclidean algorithm)

12와 18을 모두 나누는 수, 다시 말해 두 수의 공약수는 1, 2, 3, 6입니다(12의 약수⁠(divisor)⁠는 1, 2, 3, 4, 6, 12, 18의 약수는 1, 2, 3, 6, 9, 18). 그중 가장 큰 6을 12와 18의 최대공약수라 하고, $\gcd(12, 18) = 6$으로 적습니다. gcd는 영어 greatest common divisor의 머리글자입니다. 수가 커지면 약수를 하나씩 찾기가 어려워집니다. 더 빠른 길이 있을까요?

그림으로 시작합니다. $a \times b$ 직사각형에서 짧은 변을 한 변으로 하는 정사각형을 떼어 내 봅시다. $a =$ , $b =$ 입니다. 그런 정사각형을 들어가는 만큼 넣고, 남은 직사각형에서 같은 일을 되풀이합니다. 마지막에 남는 가장 작은 정사각형의 한 변이 최대공약수 입니다. 이 정사각형으로는 처음 직사각형을 빈틈없이 채울 수 있고, 그렇게 채울 수 있는 정사각형 가운데 가장 큽니다. 아래 단계 버튼으로 재생하면 정사각형을 떼어 내는 일이 한 번에 한 단계씩 나타나고, 그 아래에 같은 일을 나눗셈으로 적은 식이 한 줄씩 있습니다.

처음 값 34와 21이라면 34 = 1 × 21 + 13에서 시작해 2 = 2 × 1 + 0까지 일곱 줄이고, 나머지가 0이 되기 직전의 나머지 1이 최대공약수입니다. 줄마다 정사각형의 개수가 몫, 남은 직사각형의 짧은 변이 나머지라는 것을 그림과 맞춰 보세요.

왜 맞을까요? $q$를 들어간 정사각형의 개수(몫), $r = a - qb$를 나머지라 합시다. $a$와 $b$를 모두 나누는 수는 $r$도 나누고, 거꾸로 $b$와 $r$을 모두 나누는 수는 $a = qb + r$도 나눕니다. 그래서 정사각형을 떼어 내도 공약수의 목록은 그대로입니다. 나머지는 매번 줄어드니 언젠가 0이 되고, 그때 남은 수 $g$에 대해 $\gcd(g, 0) = g$입니다(g는 g와 0을 모두 나누는 가장 큰 수입니다). 이 과정을 한 줄로 쓰면 $\gcd(a, b) = \gcd(b,\ a \bmod b)$입니다. $a \bmod b$는 'a 모드 b'라 읽고, a를 b로 나눈 나머지를 뜻합니다. 예를 들어 $34 \bmod 21 = 13$이므로 $\gcd(34, 21) = \gcd(21, 13)$입니다. 문제를 같은 모양의 더 작은 문제로 줄이는 재귀⁠(recursion)⁠의 전형입니다.

흔히 최대공약수를 구하려면 소인수분해⁠(prime factorization)⁠가 필요하다고 생각합니다. 학교에서 12 = 2² × 3, 18 = 2 × 3²으로 나누어 공통인 2 × 3 = 6을 찾는 방법을 먼저 배우기 때문입니다. 그러나 호제법에는 소인수분해가 필요 없고, 나눗셈만 되풀이합니다. 이것이 중요한 까닭은 큰 수의 소인수분해가 빠른 방법이 알려져 있지 않을 만큼 어렵기 때문입니다. 호제법의 나눗셈 횟수는 작은 수의 자릿수의 5배를 넘지 않습니다(1844년 프랑스의 가브리엘 라메가 증명). 그래서 수백 자리 수에도 쓸 수 있고, RSA의 열쇠 계산에 쓰입니다.

각 단계의 정사각형 개수를 적어 두면 $a/b$의 연분수⁠(continued fraction)⁠가 됩니다. 마지막 단계를 빼면 매번 정사각형이 딱 하나씩만 들어가는 쌍이 이웃한 피보나치 수입니다(처음 값 34와 21이 그렇습니다). 수의 크기에 비해 단계가 가장 많은 쌍이 바로 이것이고, 라메의 한계도 여기서 나옵니다.

호제법의 나눗셈을 거꾸로 되짚으면 $ax + by = \gcd(a,b)$를 만족하는 정수⁠(integer)⁠ $x, y$를 찾을 수 있습니다. 12와 5로 해 봅시다. 나눗셈은 두 줄입니다.

$$12 = 2 \cdot 5 + 2, \qquad 5 = 2 \cdot 2 + 1$$

마지막 0 아닌 나머지가 1이니 $\gcd(12, 5) = 1$입니다. 이제 아래 줄에서 위 줄로 올라갑니다. 둘째 줄을 1에 대해 풀면 $1 = 5 - 2 \cdot 2$입니다. 첫째 줄을 2에 대해 풀면 $2 = 12 - 2 \cdot 5$이니, 이것을 넣습니다.

$$1 = 5 - 2 \cdot (12 - 2 \cdot 5) = 5 - 2 \cdot 12 + 4 \cdot 5 = 12 \cdot (-2) + 5 \cdot 5$$

그래서 x = −2, y = 5입니다. 이렇게 되짚는 계산을 확장 유클리드 호제법⁠(extended Euclidean algorithm)⁠이라 하고, 식 $ax + by = \gcd(a,b)$를 베주 항등식⁠(Bézout's identity)⁠이라 합니다. 최대공약수가 1인 두 수, 12와 5 같은 두 수를 서로소라 합니다.

이 식이 모듈러 연산⁠(modular arithmetic)⁠에서 나눗셈을 가능하게 합니다. 모듈러 연산은 어떤 수 m으로 나눈 나머지만 보는 계산이고, 이것을 '법 m으로' 계산한다고 말합니다. 시계가 12시 다음에 1시로 돌아가는 것이 법 12의 계산입니다. 위 식 $12 \cdot (-2) + 5 \cdot 5 = 1$을 12로 나눈 나머지로 보면, $12 \cdot (-2)$는 12의 배수라 사라지고 $5 \cdot 5 = 25 = 2 \cdot 12 + 1$은 나머지 1을 남깁니다. 다시 말해 법 12에서는 5를 곱하면 1이 되는 수, 5의 역수(역원⁠, inverse element⁠)가 5입니다. 같은 방법으로 $a$의 역수⁠(inverse)⁠는 $a$가 법 $m$과 서로소⁠(coprime)⁠일 때 언제나 있고, 서로소가 아니면 없습니다.

7로 나누면 2가 남고 5로 나누면 3이 남는 수처럼, 서로소인 두 수로 나눈 나머지를 동시에 맞추는 수도 확장 유클리드 호제법으로 만들 수 있습니다(중국인의 나머지 정리⁠, Chinese remainder theorem⁠). 7과 5를 되짚으면 $7 \cdot (-2) + 5 \cdot 3 = 1$입니다. 여기서 $5 \cdot 3 = 15$는 7로 나누면 1, 5로 나누면 0이 남고, $7 \cdot (-2) = -14$는 7로 나누면 0, 5로 나누면 1이 남습니다. 그러니 $2 \cdot 15 + 3 \cdot (-14) = 30 - 42 = -12$는 7로 나누면 2, 5로 나누면 3이 남습니다. 여기에 35를 더하면 23입니다. 0부터 34까지의 답은 23 하나이고, 여기에 $7 \cdot 5 = 35$의 배수⁠(multiple)⁠를 더한 수도 모두 답입니다. 실제로 23 = 3 × 7 + 2, 23 = 4 × 5 + 3입니다.

주기⁠(period)⁠에도 최대공약수와 그 짝인 최소공배수⁠(least common multiple)⁠가 나옵니다. 최소공배수는 두 수의 공통인 배수 가운데 가장 작은 수입니다. 가로로 한 번 왕복하는 데 $a$초, 세로로 한 번 왕복하는 데 $b$초($a, b$는 자연수⁠(natural number)⁠)가 걸리는 리사주 곡선⁠(Lissajous curve)⁠은 두 왕복이 동시에 끝나는 최소공배수 $ab/\gcd(a, b)$초 뒤에야 처음으로 닫힙니다(주기). 예를 들어 4초와 6초면 $24/2 = 12$초입니다.

두 수의 공약수는 모두 최대공약수를 나눕니다. 12와 18의 공약수 1, 2, 3, 6은 모두 6을 나눕니다. 그래서 최대공약수는 '다른 모든 공약수가 나누는 공약수'로 정할 수도 있습니다. 크기 비교 없이 나누어떨어짐만 쓴 정의입니다. 최소공배수도 거꾸로 '다른 모든 공배수를 나누는 공배수'입니다. 범주론⁠(category theory)⁠에서는 이렇게 정한 최대공약수를 '곱', 최소공배수를 '쌍대곱⁠(coproduct)⁠'이라 부릅니다(자세한 것은 보편 성질⁠(universal property)⁠).

$a^2 + b^2 = c^2$을 만족하는 자연수 세 쌍 가운데 3, 4, 5처럼 1 말고는 공약수가 없는 것만 찾으면, 나머지(6, 8, 10이나 9, 12, 15 등)는 모두 그 배수입니다(피타고라스 세 쌍⁠, Pythagorean triples⁠). 최대공약수가 분류의 열쇠입니다.

역사. 이 방법은 기원전 300년 무렵 유클리드가 그때까지의 기하⁠(geometry)⁠와 정수론⁠(number theory)⁠을 13권으로 정리한 책 『원론』에 실려 있습니다. 『원론』 7권은 두 수에서 작은 수를 큰 수에서 거듭 빼어 가는 방법으로 공약수를 찾고, 10권은 같은 절차를 길이에 써서 두 길이에 공통 단위가 있는지를 따집니다. 기록으로 남은 가장 오래된 알고리즘⁠(algorithm)⁠으로 흔히 꼽힙니다. 베주 항등식이라는 이름은 18세기 프랑스 수학자 에티엔 베주에게서 왔지만, 정수에 대한 이 사실은 17세기 초 프랑스의 바셰 드 메지리아크가 이미 적었습니다. 베주는 같은 생각을 다항식⁠(polynomial)⁠으로 넓혔습니다.

위의 '왜 맞을까요'는 오늘날의 말로 하면 반복문의 정확성 증명입니다. 한 단계마다 gcd(a, b)가 변하지 않는다는 것이 반복할 때마다 변하지 않는 성질, 다시 말해 반복 불변식입니다. 매번 줄어드는 음이 아닌 나머지는 반복이 언젠가 끝남을 보장하는 양(변량)입니다. 이 둘로 반복문이 옳다는 것을 보이는 것이 호어 논리⁠(Hoare logic)⁠의 틀입니다.