유클리드 호제법

Main article: Euclidean algorithm

이 글은 한글 위키피디아의 같은 제목의 기사를 발췌한 것이며, 가능한 영문 위키피디아의 번역본을 보시기 바랍니다.

유클리드 호제법(Euclidean algorithm)은 두 개의 자연수 또는 정식의 최대공약수를 구하는 알고리듬의 하나입니다. 호제법이란 말은 두 수가 서로(호) 상대방 수를 나누어(제)서 결국 원하는 수를 얻는 알고리듬을 이르는 말입니다. 두 개의 자연수(또는 다항식) $a,b$에 대해서 $a$를 $b$로 나눈 나머지를 $r$이라 하면(단, $a>b$), $a$와 $b$의 최대공약수는 $b$와 $r$의 최대공약수와 같습니다. 이 성질에 따라, $b$를 $r$로 나눈 나머지 $r'$를 구하고, 다시 $r$을 $r'$로 나눈 나머지를 구하는 과정을 반복하여 나머지가 $0$이 되었을 때 나누는 수가 $a$와 $b$의 최대공약수입니다. 이는 명시적으로 기술된 가장 오래된 알고리듬으로서도 알려져 있습니다.

예시

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21
• 42는 21로 나누어떨어집니다.

따라서, 최대공약수는 21입니다.

78696과 19332의 최대공약수를 구하면,

78696	＝	19332 × 4 ＋ 1368
19332	＝	1368 × 14 ＋ 180
1368	＝	180 × 7 ＋ 108
180	＝	108 × 1 + 72
108	＝	72 × 1 ＋ 36
72	＝	36 × 2

따라서, 최대공약수는 36입니다.

정수에 대한 유클리드 호제법

정리

$a,b\in \mathbb {Z}$이고, $a$를 $b$로 나눈 나머지가 $r$이라고 놓습니다. (여기서 $a\geq b$이고, $r$은 $0\leq r<b$인 정수.)

$a$와 $b$의 최대공약수를 $\left(a,b\right)$라고 하면, 다음이 성립합니다.

$\left(a,b\right)=\left(b,r\right).$

위에서 소개한 1071과 1029에 대한 예시를 위와 같은 표현으로 적어보면,

$\left(1071,1029\right)=\left(1029,42\right)=\left(42,21\right)=\left(21,0\right)=21$

처럼 쓸 수 있습니다.

다항식에 대한 유클리드 호제법

임의의 두 다항식에 대해서도 유클리드 호제법과 같은 원리를 사용하여, 두 다항식의 최대차수공약다항식을 구할 수 있습니다. 즉, 다음과 같은 정리가 성립합니다.

정리

$f,g\in \mathbb {R} [x]$이고, $f$를 $g$로 나눈 나머지가 $r(x)$이라고 놓습니다. (여기서 $\operatorname {deg} f\geq \operatorname {deg} g$이고, $r$은 $0\leq \operatorname {deg} r<\operatorname {deg} g$인 다항식, $\operatorname {deg} f$는 $f$의 차수를 뜻합니다.)

$f$와 $g$의 최대차수공약다항식을 $\left(f,g\right)$라고 하면, 다음이 성립합니다.

$\left(f,g\right)=\left(g,r\right)$

다항식의 경우의 예시

$f(x)=x^{3}+2x^{2}+x,g(x)=x^{2}-1$을 예로 들어 보겠습니다.

$x^{3}+2x^{2}+x=(x^{2}-1)(x+2)+(2x+2)$

$x^{2}-1=(2x+2)\left({\frac {x-1}{2}}\right)$

위 식으로부터, $\left(x^{3}+2x^{2}+x,x^{2}-1\right)=\left(x^{2}-1,2x+2\right)=\left(2x+2,0\right)=x+1$입니다.

($\mathbb {R} [x]$에서, 상수는 가역원이므로, 공약다항식에 대해서 말할 때에는 곱해주어서 계수를 조절해줄 수 있습니다.)

연분수

위에 든 예에서 나온 1071과 1029의 최대공약수를 구하는 과정은 다음과 같이 나타낼 수 있습니다.

${\begin{matrix}1071&=&1029\times 1+42\\1029&=&42\times 24+21\\42&=&21\times 2\end{matrix}}$

즉, 다음과 같이 나눗셈의 꼴로 바꾸어서 표현할 수 있습니다.

${\begin{matrix}1071/1029&=&1+42/1029\\1029/42&=&24+21/42\\42/21&=&2\end{matrix}}$

따라서, 연분수로 표현하면 다음과 같습니다.

${\frac {1071}{1029}}=1+{\frac {1}{24+{\frac {1}{2}}}}$

이와 같이, $n$와 $m\;(n>m)$의 최대공약수를 구할 때의 유클리드 호제법의 나눗셈의 모양은 유리수 $n/m$의 연분수 전개와 같습니다.

응용예제

응용예제1

다음 등식을 만족하는 자연수 $k,m$의 값을 구하여라.

$2+{\frac {1}{k+{\frac {1}{m+{\frac {1}{5}}}}}}={\frac {803}{371}}$

해설: mowoum:유클리드_호제법#응용예제1