유클리드 호제법
1. 개요
Euclidean Algorithm · —互除法
두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[1] 일본의 수학 교육과정에서는 수학A로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 '''최초'''의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.
두 양의 정수 $$a$$, $$b$$ $$(a>b)$$에 대하여 $$a=bq+r\,\left(0\leq r<b\right)$$라 하면, $$a$$, $$b$$의 최대공약수는 $$b$$, $$r$$의 최대공약수와 같다.
즉, $$\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right)$$. $$r$$=0 이라면, $$a$$, $$b$$의 최대공약수는 $$b$$가 된다.
2. 증명
$$\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$$가 서로소임을 의미한다.
3. 활용
알고리즘이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로 된 활용이 힘들다. 보통은 나머지가 [math(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$$
3.1. 최대공약수
개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 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$$
따라서 두 수의 최대공약수는 [math(1)]임을 알 수 있다.
3.2. 연분수
어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 $$\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}}$$이다.
3.3. 소스 코드
int Gcd(int a, int b)
{
int r = a % b;
if (r == 0)
return b;
else
return Gcd(b, r);
}3.3.1. C
int Euclidean(int a, int b)
{
return a%b ? Euclidean(b, a%b) : b;
}f(a,b){return b?f(b,a%b):a;}3.3.2. Python
3.3.2.1. 반복문
def Euclidean(a, b):
while b != 0:
r = a % b
a = b
b = r
return a3.3.2.2. 재귀문
def Euclidean(a, b):
r = b % a
if r == 0:
return a
else:
return Euclidean(r, a)3.4. 알고리즘으로서의 성능
두 수 $$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개로 처리할 수 있다.
4. 다항식에서의 호제법
두 정수뿐만 아니라 두 다항식의 최대공약수를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.
증명 방법 역시 정수의 경우와 동일하므로 생략한다. 단, 이 호제법이 성립하는 것은, 어디까지나 '''유클리드 정역'''의 환 위에서만이다.두 다항식 $$f\left(x\right),\ g\left(x\right)$$에 관하여, $$f\left(x\right) = g\left(x\right)Q\left(x\right)+R\left(x\right)$$이고 $$0 \le \deg\left(R\left(x\right)\right)<\deg\left(g\left(x\right)\right)$$이라 하면, $$\gcd\left(f,\ g\right) = \gcd\left(g,\ R\right)$$이 성립한다.
4.1. 예시
문제 : 두 다항식 $$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$$를 넣어서 풀면 쉽게 풀린다.
5. 유한체에서
시계 산술을 쓰는 유한체에서는 나눗셈의 정의를 다르게 정의해야 하는데, 이때 사용되는 것이 '확장된 유클리드 호제법'으로, 다음과 같이 정의된다.
이 방법을 이용해서 해당 정수의 '역수'[2]를 구한 뒤, 피제수에 곱하는 것을 유한체의 '나눗셈'으로 정의한다.$$\alpha x +\beta y = \gcd(\alpha,\,\beta)$$