유클리드 호제법

Euclidean Algorithm · —互除法

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[1] 일본의 수학 교육과정에서는 수학A로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 알려주지는 않으면서 문제는 낸다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.

$\gcd\left(a,\ b\right)=G$라 하자. 그럼 적당한 서로소인 정수 $A$, $B$에 대해 $a=GA$, $b=GB$가 성립한다. 이를 $a=bq+r$에 대입하면, $GA=GBq+r$이고, $r=G\left(A-Bq\right)$이다. 여기서 $G$는 $b$와 $r$의 공약수임을 알 수 있고, 만약 $B$와 $A-Bq$가 서로소, 즉 $\gcd\left(B,\ A-Bq\right)=1$이면 $\gcd\left(b,\ r\right)=G$이므로 증명이 끝난다.
$\gcd\left(B,\ A-Bq\right)=m$ (단, $m\neq 1$)이라고 하면, 적당한 서로소인 정수 $k$, $l$에 대해 $B=mk$, $A-Bq=ml$이 성립한다. 한편, $A=ml+Bq=ml+mkq=m\left(l+kq\right)$이다. 즉, $m$은 $A$와 $B$의 공약수임을 알 수 있다. 그런데 $A$, $B$는 서로소이므로, $m=1$이다. 이는 곧 $B$와 $A-Bq$가 서로소임을 의미한다.

알고리즘이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로 된 활용이 힘들다. 보통은 나머지가 $0$이 될 때 까지 연속해서 사용한다. 예를 들면 아래와 같다.
$\begin{aligned} b &= aq_1+r_1 \, \left(0<r_1<a\right) \\ a &= r_1 q_2+r_2 \, \left(0<r_2<r_1\right) \\ r_1 &= r_2q_3+r_3 \, \left(0<r_3<r_2\right) \\ \vdots \\ \vdots \\ r_{n-2} &= r_{n-1}q_n+r_n \, \left(0<r_n<r_{n-1}\right) \\ r_{n-1} &= r_nq_{n+1} \end{aligned} \\ \therefore \gcd\left(a,\ b\right)=r_n$

개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 12345와 1234의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
$\begin{aligned} 12345 &= 1234 \cdot 10+5 \\ 1234 &= 5 \cdot 246+4 \\ 5 &= 4 \cdot 1 + 1 \\ 4 &= 1 \cdot 4 \end{aligned} \\ \therefore \gcd \left(12345,\ 1234\right) = 1$
따라서 두 수의 최대공약수는 $1$임을 알 수 있다.

어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 $\dfrac{23}9$를 연분수 형태로 바꾼다 하자. 분자, 분모에 대해 알고리즘을 적용하면,
$\begin{aligned}23 &= 9 \cdot 2+5 \\ 9 &= 5 \cdot 1+4 \\ 5 &= 4 \cdot 1+1 \\ 4 &= 1 \cdot 4 \end{aligned}$
여기서 몫만 따오면, $\dfrac{23}9 = 2+\cfrac1{1+\cfrac1{1+\cfrac14}}$이다.

int Gcd(int a, int b)
{
	int r = a % b;
	if (r == 0)
		return b;
	else
		return Gcd(b, r);

}

손으로 계산할 때는 제수와 피제수의 값 크기를 비교해서 적절하게 배열하지만 수식이나 코드로 나타낼 때는 신경쓰지 않아도 되는데, a<b일 때 a mod b ≡ a(a%b==a)이므로 Gcd(a,b)는 Gcd(b,a)를 호출한다. 즉 재귀 과정에서 자연스럽게 큰 값이 a로, 작은 값이 b로 들어간다.

int Euclidean(int a, int b)
{
	return a%b ? Euclidean(b, a%b) : b;
}

가장 짧은 코드

f(a,b){return b?f(b,a%b):a;}

두 수 $a>b$를 나눈 나머지가 $r$이라면 황금비 $\tau = (1+\sqrt{5})/2$에 대해 $b<a/\tau$이거나 $r<a/\tau^2$ 둘 중 하나가 성립한다. (만약 $b>a/\tau$이면 $r =a-b<a/\tau^2$이기 때문) 이를 이용하면 수학적 귀납법으로 "$(a,b)$에 대해 호제법을 수행하면 나눗셈 횟수는 $\log_{\tau}(a) + 1$ 이하이다"를 보일 수 있다. 피보나치 수열의 이웃한 두 항의 경우 정확히 저 횟수만큼 나눗셈을 하게 되므로 실질적인 최소값이라 할 수 있다. 더 나아가면 주어진 $a$에 대해 나눗셈 횟수가 최대가 되는 $b$는 $\lfloor a/\tau \rfloor$ 혹은 $\lfloor a/\tau \rfloor+1$로 주어진다는 것을 보일 수 있지만 아주 중요한 것은 아니다.

어쨌든 나눗셈 횟수는 $O(\log a)$이 된다. 정수 나눗셈 1회의 복잡도가 제수와 몫의 자리수 개수에 비례한다는, 즉 $O(\log a \log (a/b))$로 나타난다는 것까지 고려하면 (자세한 과정은 생략하겠지만) 유클리드 호제법 전체의 시간 복잡도가 $O((\log a)^2)$로 나타남도 보일 수 있다. 정수의 입력 자체에서 $O(\log a)$를 쓰는 것을 감안하면 꽤 좋은 효율이다.

하지만 유클리드 호제법도 최적의 알고리즘은 아니고(!!), 정말 큰 수의 경우에는 $O(\log a(\log \log a)^2 (\log \log \log a)$ 이 보장되는 다른 준선형적 알고리즘들을 사용한다. 다행히도 2만 자리 넘어가는 정말 큰 수가 아닌 이상에야 호제법 정도면 크게 퍼포먼스가 떨어지진 않는다.

공간 복잡도 면에서는 위에 코드를 보면 알겠지만 변수 3개로도 충분하다. 다만 재귀를 쓰면 나눗셈 횟수만큼 호출 스택에서 $O(\log n)$을 잡아먹으므로 쓰지 말자. $ax+by=d$를 찾는 확장된 유클리드 알고리즘에서도 나눗셈 과정을 트랙할 필요는 없고, 코드를 잘 짜면 변수 4개로 처리할 수 있다.

두 정수뿐만 아니라 두 다항식의 최대공약수를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.

증명 방법 역시 정수의 경우와 동일하므로 생략한다. 단, 이 호제법이 성립하는 것은, 어디까지나 유클리드 정역의 환 위에서만이다.

문제 : 두 다항식 $x^3-3x^2+3x-1$, $x^2-1$의 최대공약수를 구하시오.
$x^3-3x^2+3x-1 = \left(x^2-1\right)\left(x-3\right)+\left(4x-4\right) \\ x^2-1 = \left(4x-4\right)\left(\dfrac{x+1}4\right)$
따라서, $\gcd\left(x^3-3x^2+3x-1,\ x^2-1\right) = \gcd\left(x^2-1,\ 4x-4\right) = \gcd\left(4x-4,\ 0\right) = x-1$이 처음 두 다항식의 최대공약수가 된다.
위 식에서는 원래 나머지를 비교하는 것 이기에 $x = 1$ 또는 $x=-1$를 넣어서 풀면 쉽게 풀린다.

시계 산술을 쓰는 유한체에서는 나눗셈의 정의를 다르게 정의해야 하는데, 이때 사용되는 것이 '확장된 유클리드 호제법'으로, 다음과 같이 정의된다.

이 방법을 이용해서 해당 정수의 '역수'[2]를 구한 뒤, 피제수에 곱하는 것을 유한체의 '나눗셈'으로 정의한다.