Euclidean Algorithm
개요[편집 | 원본 편집]
두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 알고리즘은 유클리드의 원론에 적혀 있는 내용으로, 인류 최초의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다. >두 양의 정수 [math]\displaystyle{ a,b\,\left(b\gt a\right) }[/math]에 대하여 [math]\displaystyle{ b=aq+r,\,\left(0\leq r\lt a\right) }[/math]라 하면, [math]\displaystyle{ a,b }[/math]의 최대공약수는 [math]\displaystyle{ a,r }[/math]의 최대공약수와 같다. 즉, [math]\displaystyle{ \gcd\left(a,b\right)=\gcd\left(a,r\right) }[/math].
증명[편집 | 원본 편집]
[math]\displaystyle{ \gcd\left(a,b\right)=G }[/math]라 하자. 그럼 적당한 서로소인 정수 [math]\displaystyle{ A,B }[/math]에 대해 [math]\displaystyle{ a=GA,\,b=GB }[/math]가 성립한다. 이를 [math]\displaystyle{ b=aq+r }[/math]에 대입하면, [math]\displaystyle{ GB=GAq+r }[/math]이고, [math]\displaystyle{ r=G\left(B-Aq\right) }[/math]이다. 여기서 [math]\displaystyle{ G }[/math]는 [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ r }[/math]의 공약수임을 알 수 있다. 만약 [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ B-Aq }[/math]가 서로소이면 증명이 끝난다. [math]\displaystyle{ \gcd\left(A,B-Aq\right)=m }[/math]이라고 하면, 적당한 서로소인 정수 [math]\displaystyle{ k,l }[/math]에 대해 [math]\displaystyle{ A=mk,\,B-Aq=ml }[/math]이 성립한다. 한편, [math]\displaystyle{ B=ml+Aq=ml+mkq=m\left(l+kq\right) }[/math]이다. 즉, [math]\displaystyle{ \gcd\left(A,B\right)=m }[/math]이다. 그런데 [math]\displaystyle{ A,B }[/math]는 서로소이므로, [math]\displaystyle{ m=1 }[/math]이다. 이는 곧 [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ B-Aq }[/math]가 서로소임을 의미한다.
활용[편집 | 원본 편집]
알고리즘이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로된 활용이 힘들다. 보통은 나머지가 0이 될 때까지 연속해서 사용한다. 이를 간단한 표로 나타내면 아래와 같다.
[math]\displaystyle{ b=aq_1+r_1,\,0\lt r_1\lt a }[/math]
[math]\displaystyle{ a=r_1q_2+r_2,\,0\lt r_2\lt r_1 }[/math]
[math]\displaystyle{ r_1=r_2q_3+r_3,\,0\lt r_3\lt r_2 }[/math]
[math]\displaystyle{ \vdots }[/math]
[math]\displaystyle{ r_{n-2}=r_{n-1}q_n+r_n,\,0\lt r_n\lt r_{n-1} }[/math]
[math]\displaystyle{ r_{n-1}=r_nq_{n+1} }[/math]
[math]\displaystyle{ \gcd\left(a,b\right)=r_n }[/math]
최대공약수[편집 | 원본 편집]
개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 12345와 1234의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
[math]\displaystyle{ 12345=1234\cdot10+5 }[/math]
[math]\displaystyle{ 1234=5\cdot246+4 }[/math]
[math]\displaystyle{ 5=4\cdot1+1 }[/math]
[math]\displaystyle{ 4=1\cdot4 }[/math]
곧 두 수의 최대공약수는 1임을 알 수 있다.
연분수[편집 | 원본 편집]
어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 [math]\displaystyle{ \frac{23}{9} }[/math]를 연분수 형태로 바꾼다 하자. 분자, 분모에 대해 알고리즘을 적용하면,
[math]\displaystyle{ 23=9\cdot2+5 }[/math]
[math]\displaystyle{ 9=5\cdot1+4 }[/math]
[math]\displaystyle{ 5=4\cdot1+1 }[/math]
[math]\displaystyle{ 4=1\cdot4 }[/math]
여기서 몫만 따오면, [math]\displaystyle{ \frac{23}{9}=2+\frac{1}{1+\frac{1}{1+\frac{1}{4}} } }[/math]이다.
다항식에서의 호제법[편집 | 원본 편집]
개요에도 써있지만, 두 정수뿐만 아니라 두 다항식의 최대공약수를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.
두 다항식 [math]\displaystyle{ f\left(x\right),g\left(x\right) }[/math]에 관하여, [math]\displaystyle{ f\left(x\right)=g\left(x\right)q\left(x\right)+r\left(x\right),\,0\leq\deg{r\left(x\right)}\lt \deg{g\left(x\right)} }[/math]이라 하면, [math]\displaystyle{ \gcd\left(f,g\right)=\gcd\left(g,r\right) }[/math]이 성립한다.
증명 방법 역시 정수의 경우와 동일하므로 생략한다.
예시[편집 | 원본 편집]
[math]\displaystyle{ x^3-3x^2+3x-1,\,x^2-1 }[/math]의 최대공약수를 구해보자. 그럼,
[math]\displaystyle{ x^3-3x^2+3x-1=\left(x^2-1\right)\left(x-3\right)+\left(4x-4\right) }[/math]
[math]\displaystyle{ x^2-1=\left(4x-4\right)\left(\frac{x+1}{4}\right) }[/math]
따라서, [math]\displaystyle{ \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]이 처음 두 다항식의 최대공약수가 된다.