유클리드 호제법 (r0 버전으로 되돌리기)

[include(틀:대수학)]
[include(틀:정수론)]
[목차]
== 개요 ==
{{{+1 유클리드 [[互]][[除]][[法]] / Euclidean algorithm}}}

두 양의 정수, 혹은 두 다항식의 [[최대공약수]]를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않으나(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[* 그렇다고 아주 접하지 않는 건 아닌데, 사교육을 받지 않은 구세대라면 방학교재에서 봤을 것이다.] 정수론을 배우게 된다면 가장 먼저 나올 확률이 높은 공식이다. 일본의 수학 교육과정에서는 [[수학A]]로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 [[알고리즘]]은 [[유클리드]]의 원론에 적혀있는 내용으로, 인류 '''최초'''의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.
>'''유클리드 호제법'''
>----
>두 양의 정수 [math(a,b\ (a>b))]에 대하여 [math(a=bq+r\,\left(0\le r<b\right))][* 혹은 [math(a\equiv r\left(\text{mod}\,b\right))]. ]이라 하면, [math(a,b)]의 [[최대공약수]]는 [math(b,r)]의 [[최대공약수]]와 같다. 즉,{{{#!wiki style="margin:10px 0;text-align:center"
[math(\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right))]}}}[math(r=0)]이라면, [math(a,b)]의 [[최대공약수]]는 [math(b)]가 된다.

== 증명 ==
[math(\gcd\left(a,\ b\right)=G)], [math(\gcd\left(b,\ r\right)=G')]이라 하자. 적당한 [[서로소]]인 [[정수]] [math(A,B)]에 대해 [math(a=GA,b=GB)]가 성립한다. 이를 [math(a=bq+r)]에 대입하면, [math(GA=GBq+r)]이고, [math(r=G\left(A-Bq\right))]이다. 여기서 [math(G)]는 [math(b)]와 [math(r)]의 공약수임을 알 수 있다. 즉, [math(G)]는 [math(G')]의 약수이다.

[math(G'=mG)]로 두자. 그러면 적당한 서로소인 두 [[정수]] [math(k,l)]에 대해 [math(GB=G'k=Gmk, G(A-Bq)=G'l=Gml)]이 성립한다. 
양변을 [math(G)]로 나누면 [math(B=mk, A-Bq=ml)]이다.
[math(A=ml+Bq=ml+mkq=m\left(l+kq\right))]에서 [math(m)]은 [math(A)]와 [math(B)]의 공약수인데, [math(gcd(A,B)=1)]이므로 항상 [math(m=1)]이고 [math(G'=G)]이다.

== 활용 ==
[[알고리즘]]이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로 된 활용이 힘들다. 보통은 나머지가 [math(0)]이 될 때 까지 연속해서 사용한다. 예를 들면 아래와 같다.
||<tablealign=center><tablebordercolor=#fff,#1f2023><tablebgcolor=#fff,#1f2023> [math(\begin{aligned}a&=bq_1+r_1\,\left(0<r_1<b\right)\\b&=r_1q_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\\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)] ||

=== [[최대공약수]] ===
개요에도 쓰여있듯이, 이 알고리즘은 두 수의 [[최대공약수]]를 구할 때 쓸 수 있다. 한 예로 [math(12345)]와 [math(1234)]의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
||<tablealign=center><tablebordercolor=#fff,#1f2023><tablebgcolor=#fff,#1f2023> [math(\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)]]]임을 알 수 있다 (relatively prime).

=== 연분수 ===
어떤 [[분수(수학)|분수]]를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 [math(\dfrac{23}9)]를 연분수 형태로 바꾼다 하자. [[분자]], [[분모]]에 대해 알고리즘을 적용하면,
||<tablealign=center><tablebordercolor=#fff,#1f2023><tablebgcolor=#fff,#1f2023> [math(\begin{aligned}23&=9\cdot 2+5\\9&=5\cdot 1+4\\5&=4\cdot 1+1\\4&=1\cdot 4\end{aligned})] ||
여기서 몫만 따오면, [math(\dfrac{23}9=2+\cfrac1{1+\cfrac1{1+\cfrac14}})]이다.

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

==== C ====
{{{#!syntax cpp
int Euclidean(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}
}}}

===== [[숏코딩]] =====
{{{#!syntax cpp
f(a,b){return b?f(b,a%b):a;}
}}}

==== Python ====
===== 반복문 =====
{{{#!syntax python
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a
}}}

===== 재귀문 =====
{{{#!syntax python
def Euclidean(a, b):
    r = b % a
    if r == 0:
        return a
    return Euclidean(r, a)
}}}

==== Java ====
{{{#!syntax java
int Euclidean(int a, int b) {
    if (b == 0)
        return a;
    return Euclidean(b, a % b);
}
}}}

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

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

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

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

== 다항식에서의 호제법 ==
두 정수뿐만 아니라 두 [[다항식]]의 [[최대공약수]]를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.
>두 다항식 [math(f\left(x\right),\ g\left(x\right))]에 관하여, [math(f\left(x\right)=g\left(x\right)Q\left(x\right)+R\left(x\right))]이고 [math(0\le\deg\left(R\left(x\right)\right)<\deg\left(g\left(x\right)\right))]이라 하면, [math(\gcd\left(f,\ g\right)=\gcd\left(g,\ R\right))]이 성립한다.
증명 방법 역시 정수의 경우와 동일하므로 생략한다. 단, 이 호제법이 성립하는 것은, 어디까지나 '''유클리드 정역'''의 [[환(대수학)|환]] 위에서만이다.

=== 예시 ===
>'''문제'''
>----
>두 다항식 [math(x^3-3x^2+3x-1)], [math(x^2-1)]의 최대공약수를 구하시오.

>'''풀이'''
>----
>{{{#!wiki style="text-align: center"
[math(x^3-3x^2+3x-1=\left(x^2-1\right)\left(x-3\right)+\left(4x-4\right))]}}}
>{{{#!wiki style="text-align: center"
[math(x^2-1=\left(4x-4\right)\left(\dfrac{x+1}4\right))]}}}
>따라서, [math(\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)]이 처음 두 [[다항식]]의 최대공약수가 된다.
위 식에서는 원래 나머지를 비교하는 것이기에 [math(x=1)] 또는 [math(x=-1)]를 넣어서 풀면 쉽게 풀린다.

== [[유한체]]에서[anchor(확장된 유클리드 호제법)] ==
[[시계 산술]]을 쓰는 [[유한체]]에서는 [[나눗셈]]의 정의를 다르게 정의해야 하는데, 이때 사용되는 것이 '확장된 유클리드 호제법'으로, 다음과 같이 정의된다.
>[math(\alpha x+\beta y=\gcd(\alpha,\,\beta))]
이 방법을 이용해서 해당 정수의 '[[역수]]'[* [[유리수|유리수체]]에서의 역수와는 다르다. 유리수체에서의 정수의 역수는 1보다 작을 수 밖에 없는데, 유한체의 역수는 유한체 내부의 원소여야 하기 때문에 1보다 클 수 밖에 없다. 예를 들어서 5를 법으로 하는 유한체의 경우, 1의 역원은 1이지만 2의 역원은 3, 3의 역원은 2, 4의 역원은 4 자기 자신이 된다.]를 구한 뒤, 피제수에 곱하는 것을 유한체의 '나눗셈'으로 정의한다.

== 관련 문서 ==
 * [[최대공약수]]
 * [[나눗셈 정리]]
 * [[나머지 정리]]
 * [[베주 항등식]]

[[분류:정수론]][[분류:대수학]][[분류:알고리즘]]
유클리드 호제법 (r0 버전으로 되돌리기)

캡챠
