유클리드 호제법

Euclidean Algorithm

개요

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

증명

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

활용

알고리즘이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로된 활용이 힘들다. 보통은 나머지가 0이 될 때까지 연속해서 사용한다. 이를 간단한 표로 나타내면 아래와 같다.

$b=aq_{1}+r_{1},\,0<r_{1}<a$ $a=r_{1}q_{2}+r_{2},\,0<r_{2}<r_{1}$ $r_{1}=r_{2}q_{3}+r_{3},\,0<r_{3}<r_{2}$ $\vdots$ $r_{n-2}=r_{n-1}q_{n}+r_{n},\,0<r_{n}<r_{n-1}$ $r_{n-1}=r_{n}q_{n+1}$ $\gcd \left(a,b\right)=r_{n}$

최대공약수

개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 12345와 1234의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면, $12345=1234\cdot 10+5$
$1234=5\cdot 246+4$
$5=4\cdot 1+1$
$4=1\cdot 4$ 곧 두 수의 최대공약수는 1임을 알 수 있다.

연분수

어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 ${\frac {23}{9}}$를 연분수 형태로 바꾼다 하자. 분자, 분모에 대해 알고리즘을 적용하면, $23=9\cdot 2+5$
$9=5\cdot 1+4$
$5=4\cdot 1+1$
$4=1\cdot 4$ 여기서 몫만 따오면, ${\frac {23}{9}}=2+{\frac {1}{1+{\frac {1}{1+{\frac {1}{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\leq \deg {r\left(x\right)}<\deg {g\left(x\right)}$이라 하면, $\gcd \left(f,g\right)=\gcd \left(g,r\right)$이 성립한다.

증명 방법 역시 정수의 경우와 동일하므로 생략한다.

예시

$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({\frac {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$이 처음 두 다항식의 최대공약수가 된다.

관련 문서

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