Processing math: 8%

유클리드 호제법

Euclidean Algorithm

1 개요

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

두 양의 정수 a,b(b\gta)에 대하여 b=aq+r,(0r\lta)라 하면, a,b최대공약수a,r최대공약수와 같다. 즉, gcd.

2 증명

\gcd\left(a,b\right)=G라 하자. 그럼 적당한 서로소정수 A,B에 대해 a=GA,\,b=GB가 성립한다. 이를 b=aq+r에 대입하면, GB=GAq+r이고, r=G\left(B-Aq\right)이다. 여기서 Gar의 공약수임을 알 수 있다. 만약 AB-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이다. 이는 곧 AB-Aq가 서로소임을 의미한다.

3 활용

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

b=aq_1+r_1,\,0\ltr_1\lta
a=r_1q_2+r_2,\,0\ltr_2\ltr_1
r_1=r_2q_3+r_3,\,0\ltr_3\ltr_2
\vdots
r_{n-2}=r_{n-1}q_n+r_n,\,0\ltr_n\ltr_{n-1}
r_{n-1}=r_nq_{n+1}
\gcd\left(a,b\right)=r_n

3.1 최대공약수

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

3.2 연분수

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

3.3 소스 코드

3.3.1 C

int Euclidean(int a, int b)
{
return b ? Euclidean(b, a%b) : a;
}

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)}\lt\deg{g\left(x\right)}이라 하면, \gcd\left(f,g\right)=\gcd\left(g,r\right)이 성립한다.

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

4.1 예시

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

5 관련 항목