유클리드 호제법 문서 원본 보기



Euclidean Algorithm

== 개요 ==
두 양의 정수, 혹은 두 다항식의 [[최대공약수]]를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 [[알고리즘]]은 [[유클리드]]의 원론에 적혀 있는 내용으로, 인류 '''최초'''의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.
>두 양의 정수 <math>a,b\,\left(b> a\right)</math>에 대하여 <math>b=aq+r,\,\left(0\leq r< a\right)</math>라 하면, <math>a,b</math>의 [[최대공약수]]는 <math>a,r</math>의 [[최대공약수]]와 같다. 즉, <math>\gcd\left(a,b\right)=\gcd\left(a,r\right)</math>.

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

== 활용 ==
[[알고리즘]]이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로된 활용이 힘들다. 보통은 나머지가 0이 될 때까지 연속해서 사용한다. 이를 간단한 표로 나타내면 아래와 같다.
{{인용문2|<math>b=aq_1+r_1,\,0< r_1< a</math> <br /> <math>a=r_1q_2+r_2,\,0< r_2< r_1</math> <br /> <math>r_1=r_2q_3+r_3,\,0< r_3< r_2</math> <br /> <math>\vdots</math> <br /> <math>r_{n-2}=r_{n-1}q_n+r_n,\,0< r_n< r_{n-1}</math> <br /> <math>r_{n-1}=r_nq_{n+1}</math> <br /> <math>\gcd\left(a,b\right)=r_n</math>}}

=== [[최대공약수]] ===
개요에도 쓰여있듯이, 이 알고리즘은 두 수의 [[최대공약수]]를 구할 때 쓸 수 있다. 한 예로 12345와 1234의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
<math>12345=1234\cdot10+5</math> <br /> <math>1234=5\cdot246+4</math> <br /> <math>5=4\cdot1+1</math> <br /> <math>4=1\cdot4</math>
곧 두 수의 최대공약수는 1임을 알 수 있다.

=== 연분수 ===
어떤 [[분수 (수학)|분수]]를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 <math>\frac{23}{9}</math>를 연분수 형태로 바꾼다 하자. [[분자]], [[분모]]에 대해 알고리즘을 적용하면,
<math>23=9\cdot2+5</math> <br /> <math>9=5\cdot1+4</math> <br /> <math>5=4\cdot1+1</math> <br /> <math>4=1\cdot4</math>
여기서 몫만 따오면, <math>\frac{23}{9}=2+\frac{1}{1+\frac{1}{1+\frac{1}{4}} }</math>이다.

== 다항식에서의 호제법 ==
개요에도 써있지만, 두 정수뿐만 아니라 두 [[다항식]]의 [[최대공약수]]를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.
{{인용문2|두 다항식 <math>f\left(x\right),g\left(x\right)</math>에 관하여, <math>f\left(x\right)=g\left(x\right)q\left(x\right)+r\left(x\right),\,0\leq\deg{r\left(x\right)}<\deg{g\left(x\right)}</math>이라 하면, <math>\gcd\left(f,g\right)=\gcd\left(g,r\right)</math>이 성립한다.}}
증명 방법 역시 정수의 경우와 동일하므로 생략한다.

=== 예시 ===
<math>x^3-3x^2+3x-1,\,x^2-1</math>의 최대공약수를 구해보자. 그럼,
<math>x^3-3x^2+3x-1=\left(x^2-1\right)\left(x-3\right)+\left(4x-4\right)</math> <br /> <math>x^2-1=\left(4x-4\right)\left(\frac{x+1}{4}\right)</math>
따라서, <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>이 처음 두 [[다항식]]의 최대공약수가 된다.

== 관련 문서 ==
* [[최대공약수]]
* [[나눗셈 정리]]
* [[나머지 정리]]
* [[라메의 정리]] - 유클리드 호제법을 수행하는 데 필요한 최소 횟수에 관한 정리이다.

[[분류:정수론]]