[include(틀:대수학)] [include(틀:정수론)] [목차] == 개요 == {{{+1 Euclidean Algorithm · —[[互]][[除]][[法]]}}} 두 양의 정수, 혹은 두 다항식의 [[최대공약수]]를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[* 그렇다고 아주 접하지 않는 건 아닌데, 사교육을 받지 않은 구세대라면 방학교재에서 봤을 것이다.] 일본의 수학 교육과정에서는 [[수학A]]로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. --[[인성 | 알려주지는 않으면서 ]][[인성질 | 문제는 낸다.]]-- 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 [[알고리즘]]은 [[유클리드]]의 원론에 적혀있는 내용으로, 인류 '''최초'''의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다. >두 양의 정수 [math(a)], [math(b)] [math((a>b))]에 대하여 [math(a=bq+r\,\left(0\leq r<b\right))]라 하면, [math(a)], [math(b)]의 [[최대공약수]]는 [math(b)], [math(r)]의 [[최대공약수]]와 같다.[br]즉, [math(\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right))]. [math(r)]=0 이라면, [math(a)], [math(b)]의 [[최대공약수]]는 [math(b)]가 된다. == 증명 == [math(\gcd\left(a,\ b\right)=G)]라 하자. 그럼 적당한 [[서로소]]인 [[정수]] [math(A)], [math(B)]에 대해 [math(a=GA)], [math(b=GB)]가 성립한다. 이를 [math(a=bq+r)]에 대입하면, [math(GA=GBq+r)]이고, [math(r=G\left(A-Bq\right))]이다. 여기서 [math(G)]는 [math(b)]와 [math(r)]의 공약수임을 알 수 있고, 만약 [math(B)]와 [math(A-Bq)]가 서로소, 즉 [math(\gcd\left(B,\ A-Bq\right)=1)]이면 [math(\gcd\left(b,\ r\right)=G)]이므로 증명이 끝난다. [math(\gcd\left(B,\ A-Bq\right)=m)] (단, [math(m\neq 1)])이라고 하면, 적당한 서로소인 [[정수]] [math(k)], [math(l)]에 대해 [math(B=mk)], [math(A-Bq=ml)]이 성립한다. 한편, [math(A=ml+Bq=ml+mkq=m\left(l+kq\right))]이다. 즉, [math(m)]은 [math(A)]와 [math(B)]의 공약수임을 알 수 있다. 그런데 [math(A)], [math(B)]는 서로소이므로, [math(m=1)]이다. 이는 곧 [math(B)]와 [math(A-Bq)]가 서로소임을 의미한다. == 활용 == [[알고리즘]]이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로 된 활용이 힘들다. 보통은 나머지가 [math(0)]이 될 때 까지 연속해서 사용한다. 예를 들면 아래와 같다. [math(\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의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면, [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)]]]임을 알 수 있다. === 연분수 === 어떤 [[분수(수학)|분수]]를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 [math(\dfrac{23}9)]를 연분수 형태로 바꾼다 하자. [[분자]], [[분모]]에 대해 알고리즘을 적용하면, [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}})]이다. === 소스 코드 === {{{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로 들어간다. ==== 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;} }}} ==== Python ==== ===== 반복문 ===== {{{def Euclidean(a, b): while b != 0: r = a % b a = b b = r return a }}} ===== 재귀문 ===== {{{def Euclidean(a, b): r = b % a if r == 0: return a else: return Euclidean(r, a) }}} === [[알고리즘]]으로서의 성능 === 두 수 [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(O(\log a))]이 된다. 정수 나눗셈 1회의 복잡도가 제수와 몫의 자리수 개수에 비례한다는, 즉 [math(O(\log a \log (a/b)))]로 나타난다는 것까지 고려하면 (자세한 과정은 생략하겠지만) 유클리드 호제법 전체의 [[시간 복잡도]]가 [math(O((\log a)^2))]로 나타남도 보일 수 있다. 정수의 입력 자체에서 [math(O(\log a))]를 쓰는 것을 감안하면 꽤 좋은 효율이다. 하지만 유클리드 호제법도 최적의 알고리즘은 아니고(!!), 정말 큰 수의 경우에는 [math(O(\log a(\log \log a)^2 (\log \log \log a))] 이 보장되는 다른 준선형적 알고리즘들을 사용한다. 다행히도 2만 자리 넘어가는 정말 큰 수가 아닌 이상에야 호제법 정도면 크게 퍼포먼스가 떨어지진 않는다. 공간 복잡도 면에서는 위에 코드를 보면 알겠지만 변수 3개로도 충분하다. 다만 재귀를 쓰면 나눗셈 횟수만큼 호출 스택에서 [math(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)]의 최대공약수를 구하시오. [math(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))] 따라서, [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 자기 자신이 된다.]를 구한 뒤, 피제수에 곱하는 것을 유한체의 '나눗셈'으로 정의한다. == 관련 문서 == * [[최대공약수]] * [[나눗셈 정리]] * [[나머지 정리]] * [[베주 항등식]] [[분류:정수론]][[분류:대수학]][[분류:알고리즘]]