유클리드 호제법

• 상위 항목: 수학, 수학 관련 정보, 정수론

Euclidean Algorithm

1 개요

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

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

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)$$ 이다. 여기서 $$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$$ 가 서로소임을 의미한다.

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 관련 항목

• 최대공약수
• 나눗셈 정리
• 나머지 정리