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